D - Grid Repainting

コメント歓迎です。

以前に解いた幅優先探索の応用問題です。

以前の記事：C - 幅優先探索 - 思考する三角形▽

問題

abc114.contest.atcoder.jp

方針

この問題のポイントは2つあります。

①塗りつぶすマスをうまく計算する
②幅優先探索でゴールまでの最短手数を見つける

まず、黒く塗りつぶせるマスの最大数をどうやって計算するか考える必要があります。

すべてのマスの数は入力条件からで計算できます。

また、最初から黒いマス('#')の数も入力からわかります。

つまり、新たに黒く塗りつぶせるマスは「すべてのマス」ー「最初から黒いマス」ー「通り道の白いマス」となります。

黒く塗りつぶせるマスの数が最大となるのは、白のマスが最小の場合です。

ここで②の幅優先探索の話になります。

白のマスを最少にするためはスタートからゴールまで最短手数のルートを見つける必要があります。

最少ルートを探す方法が幅優先探索ということになります。

コード(AC)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 宣言
string maze[50]; // 迷路データ
int H; // 高さ
int W; // 幅
int scount = 0; // '#'の数
int ans = 0;
  
vector< vector<int> > score(50, vector<int> (50, 0)); // 手数
bool visited[50][50]; // 訪問履歴
const int dh[] = {1, -1, 0, 0};
const int dw[] = {0, 0, 1, -1};
  
// 幅優先探索
void bfs(int i, int j) {
  // キューを準備
  queue<pair<int,int> > Q;
  // スタート地点のスコアを0にセット
  score[i][j] = 0;
  // スタート地点の座標をキューにプッシュ
  Q.push(make_pair(i, j));
  // キューが空になるまで処理を実行
  while(!Q.empty()) {
    // 探索の起点となる座標を記憶してからポップ
    pair<int,int> q = Q.front();
    Q.pop();
    int h = q.first;
    int w = q.second;
    // 起点を元に座標を移動
    for (int k = 0; k < 4; k++) {
      int nh = h + dh[k];
      int nw = w + dw[k];
      // 移動先が迷路の範囲外なら処理をスキップ
      if (nh < 0 || nh >= H || nw < 0 || nw >= W) {
        continue;
      }
      // 移動先が壁か訪問済みなら処理をスキップ
      if (maze[nh][nw] == '#' || visited[nh][nw]) {
        continue;
      }
      // 移動先のスコアを起点のスコア+1にする
      score[nh][nw] = score[h][w] + 1;
      // 移動先の座標を訪問済みにする
      visited[nh][nw] = true;
      // 訪問先の座標をキューにプッシュ(順番が来たら探索の起点になる)
      Q.push(make_pair(nh, nw));
    }
  }
}
  
int main() {
  // 入力
  cin >> H >> W;
  // 迷路データ
  for (int i = 0; i < H; i++ ) {
    cin >> maze[i]; 
  }
  
  // 幅優先探索
  bfs(0, 0);
  
  // '#'の数をカウント
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (maze[i][j] == '#') {
        scount++;
      }
    }
  }
  // ゴールにたどり着けなかった場合
  if (score[H - 1][W - 1] == 0) {
    ans = -1;
  }
  // ゴールにたどり着けた場合
  else {
    ans = H * W - scount -(score[H - 1][W - 1] + 1);
  }
  
  // 出力
  cout << ans << endl;
  return 0;
}