Grid Repainting [AtCoder Beginner Contest 088 D]

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

解法

https://abc088.contest.atcoder.jp/submissions/2109769

少し複雑なので、もう少し簡単に考えてみよう。
(0,0)から(W-1,H-1)までのパスが作れないなら"-1"
もし、作れるなら、そのパス以外を塗りつぶすとスコアが出せる。
スコアを最大化したいなら、なるべくパスが短い方がいい。
その為、計算の為に(0,0)から(W-1,H-1)への最短距離を計算し、
「W*H - (最短距離) - (黒マスの数)」を求めると答え。
　
最短距離は幅優先探索で探していく。
練習問題 解説

int H, W;
string B[50];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
int vis[55][55];
int dp[55][55];
int check() {
    queue<pair<int, int>> que;
    que.push({ 0, 0 });
    vis[0][0] = 1;
    while (!que.empty()) {
        auto q = que.front(); que.pop();
        int x, y;
        tie(x, y) = q;
 
        if (x == W - 1 and y == H - 1) return dp[y][x];
 
        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                if (B[yy][xx] == '.' and vis[yy][xx] == 0) {
                    vis[yy][xx] = 1;
                    dp[yy][xx] = dp[y][x] + 1;
                    que.push({ xx, yy });
                }
            }
        }
    }
 
    return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> B[y];
 
    int ans, res = check();
    if (!res) ans = -1;
    else {
        ans = H * W - res - 1;
        rep(y, 0, H) rep(x, 0, W) if (B[y][x] == '#') ans--;
    }
 
    printf("%d\n", ans);
}