問題概要

$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;
}

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

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

AtCoder ABC 088 D - Grid Repainting (緑色, 400 点)

問題概要

制約

考えたこと