ABC 088: D - Grid Repainting で BFS の特徴を学ぶ

問題

入力例を眺めてみる。

思考のプロセス

・まずはゴール到達可否を判定
 BFS で探索してみた。

bfs.cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int H, W;

int main() {
	cin >> H >> W;
	vector<string>S(H);
	vector<vector<int>>memo(H, vector<int>(W, -1)); memo[0][0] = 0;
	for (int i = 0; i < H; i++)
		cin >> S[i];

	queue<pair<int, int>>que;
	que.push(pair(0, 0));
	vector<pair<int, int>>direction{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

while (!que.empty()) {
	int y = que.front().first;
	int x = que.front().second;
	que.pop();
	for (auto dn : direction) {
		int dy = y + dn.first;
		int dx = x + dn.second;

		if ((0 <= dy && dy < H) && (0 <= dx && dx < W) \
			&& S[dy][dx] == '.' && memo[dy][dx] == -1) {
			memo[dy][dx] = memo[y][x] + 1;
			que.push(pair(dy, dx));
		}

	}

}

if (memo[H - 1][W - 1] == -1)
   cout << "fail";//探索失敗
else 
   cout << "true" //探索成功

while (1) {}
return 0;
}

・不要な白のカウント方法を思案
 アイディア1: メモから重複した要素数をカウント
       BFS は、今まで通った道をメモし、何個歩いたかカウントしています。
       以下 入力例 1 で、メモした結果を共有します。

image.cpp

//    input         
//    .  .  #         
//    #  .  .
//    .  .  .

//    memo          
//    1  2 -1   <=最短経路とは別に
//   -1  3  4   <=重複している数字がある。BFS 動作で必ず発生する。
//    5  4  5   <=重複している要素をカウントすれば不要な白を炙り出せるのでは？

       考察の結果、不採用!
       理由としては入力例2のような紫領域をカウント出来ないから
        
       # で囲まれた領域は探索していないので、メモ上では "-1" となっている。
       だから重複要素のカウントとしては不十分、だから不採用。

 アイディア2: アイディア1 + "#" で囲まれた領域をカウント
       オレンジ色の数を追加でカウントするイメージです。
       但し、赤色の領域には注意が必要です。

       入力例2における最短ルートは 46 です。
       単純に 46 以下の数字の重複を考えると赤領域のカウントが漏れてしまいます。

        ただ、もっとシンプルに考察できないでしょうか。
       そもそも BFS のメリットは何？
       そう、最短ルートを求めることが出来る事です。
       その特徴を活かしたアプローチはないのでしょうか!?

 アイディア3: 白の総数 - 最短ルート
       46 個の白があれば Goal です。
       っであれば、それ以外の白の合算が答えでは！？

まとめ

 以下、共に AC でした。
 アイディア 2: https://atcoder.jp/contests/abc088/submissions/35911480
 アイディア 3: https://atcoder.jp/contests/abc088/submissions/35908714

 "BFS では最短ルートを探せる。"
 胸に刻むことが出来て良かったです。
 出会いに感謝 m(_ _)m

おまけ

 なぜ、BFS は最短ルートを割り出せるのでしょうか。
 それは、先着順にルートを割り振っており、
 一度訪問したところはカウントをしません。
 これにより、最短ルートを最低でも 1 本、探すことが出来るからです。