ABC088 D:Grid Repainting

競技プログラミング

drkenさんによると、「予め盤面をいじるタイプの問題は今後よく出て」くるとのこと。頑張ろう。

https://atcoder.jp/contests/abc088/tasks/abc088_d

経路復元なるものをしなければならないかと思ったが、よく考えればそんなややこしいことをする必要はない。

ゴールにたどり着いた時の最短路 + 1（この1は始点のマス） がそのまま実際に通った白マスの個数になるのだから、あとはこの数値で白マス全体の個数を減らせば、それがそのまま答えとなる。

template <class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

int H, W, N;
vector<vector<char>> g_graph;
vector<vector<int>> g_distance;
const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};

void bfs(const int gy, const int gx) {
    g_distance[0][0] = 0;
    queue<P> q;
    q.push(P(0, 0));
    while (!q.empty()) {
        P now = q.front();
        q.pop();
        int y = now.first, x = now.second;
        if (y == gy && x == gx) {
            break;
        }

        rep(i, 4) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny < 0 || ny >= H || nx < 0 || nx >= W) {
                continue;
            }
            if (g_graph[ny][nx] == '#') {
                continue;
            }

            if (chmin(g_distance[ny][nx], g_distance[y][x] + 1)) {
                q.push(P(ny, nx));
            }
        }
    }
}

signed main() {
    cin >> H >> W;
    g_graph.assign(H + 10, vector<char>(W + 10));
    int white = 0;
    rep(i, H) {
        rep(j, W) {
            char c;
            cin >> c;
            g_graph[i][j] = c;
            if (c == '.') {
                white++;
            }
        }
    }

    g_distance.assign(H + 10, vector<int>(W + 10, INF));
    bfs(H - 1, W - 1);
    if (g_distance[H - 1][W - 1] != INF) {
        int ans = white - g_distance[H - 1][W - 1] - 1;
        cout << ans << endl;
    } else {
        puts("-1");
    }
}

解いた問題数がまだまだ少ないためなんともいえないが、おそらく「予め盤面をいじるタイプの問題」というのは最適解を出しきってからいじってもいいのだろう。