けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 088 D - Grid Repainting (400 点)

グリッド上をスタートからゴールまで行く系の問題において、しばしばある

  • 盤面に対し、何らかの形でコストを払ったりスコアを獲得したりしながら変更を加えられる

という設定の問題。その設定が加わると難しい問題になることも多いが、この問題は比較的素直な部類ではある。

問題へのリンク

問題概要

 H ×  W のグリッドが与えられる。
グリッドの各マスは「白」か「黒」に塗られている。今、( 1, 1) マスから ( H, W) マスまで進みたい。ただし「白」のマスしか通ることはできない。

スタートする前に、白いマスを黒いマスに予め変更することができる。1 マス変更するたびに 1 のスコアが加算される。

スタートからゴールまで白いマスのみを通ってゴールできる状態を維持しながら、最大でどれだけのスコアを獲得できるかを求めよ。ただし初期盤面の時点ですでにゴール不可能な場合は -1 を出力せよ。

制約

  •  H, W \le 50

考えたこと

盤面の変え方を全探索したのではとても間に合わない。このタイプの「スタートからゴールまで進むけど、予めか途中か、盤面を変えてしまえる」というタイプの問題では

  • スタートからゴールまで進む探索をやりながら、盤面変化も同時に扱ってしまう
  • スタートからゴールまで進む経路を固定してみたときに、盤面変更コストはどれだけ払わなければならないかを考える

というフレームワークの手法が解法になることが多い気がする。この問題も例外にあらず。

特に太字の考察は肝な気がしていて、この問題はそれですぐに解ける。スタートからゴールまでの経路を決めると、その経路以外のマスをすべて黒く塗るのがよい。

つまり、

  • スタートからゴールまで行ける「白」マスのみの経路のうち、「経路外のマスの個数から黒マスの個数を引いたもの」を最大化せよ

という問題になった。これはつまり

  • スタートからゴールまで行ける「白」マスのみの経路のうち、「白マス」の個数が最小となるものを求めよ。

という問題である。これは幅優先探索で自然に解くことができる。

まとめると

  • スタートからゴールまで白マスのみを通って行ける経路のうち、白マスの個数が最小のものを求める
  • 盤面全体の白マスの個数から、その最小値を引いた値が答え
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
using pint = pair<int,int>;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int H, W;
string fi[110];
int dist[110][110]; // BFS 用

int main() {
    // 入力
    cin >> H >> W;
    int wnum = 0;
    for (int i = 0; i < H; ++i) {
        cin >> fi[i];
        for (int j = 0; j < W; ++j) {
            if (fi[i][j] == '.') ++wnum;
        }
    }

    // BFS
    memset(dist, -1, sizeof(dist));
    dist[0][0] = 1;
    queue<pint> que;
    que.push(pint(0, 0));
    while (!que.empty()) {
        pint cur = que.front();
        que.pop();
        int x = cur.first;
        int y = cur.second;
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (fi[nx][ny] == '#') continue;
            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                que.push(pint(nx, ny));
            }
        }
    }
    if (dist[H-1][W-1] == -1) cout << -1 << endl;
    else  cout << wnum - dist[H-1][W-1] << endl;
}