幅優先探索の一般的な罠

幅優先探索でTLEする一般的な罠の解説です。
こういうグリッドを幅優先する問題で起こりやすいですね。
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder


簡単のためこのような迷路を考えます。(#壁、.通行可)

/abcdef
1######
2####G#
3###..#
4##...#
5#...##
6#S.###
7######

この迷路の幅優先探索は本来こうあるべきです

{(b,6)}
->{(b,5),(c,6)}
->{(c,5)}
->{(c,4),(d,5)}
->{(d,4)}
->{(e,4),(d,3)}

ところが、このようなコードを書くと

struct Point {
	int y, x;
};
char map[100][100];             //HW '.'通行可、'#'通行不可
bool visited[100][100] = {};    //HW 確認したらtrueに
int  dist[100][100];            //HW Sからの距離

que.push(S);
dist[S.y][S.x] = 0; visited[S.y][S.x] = true;
while (!que.empty()) {
	Point now = que.front(); que.pop();
	visited[now.y][now.x] = true;
	const int diff[] = { 1,0,-1,0,1 };
	for (int i = 0; i < 4; ++i) {
		int nexty = now.y + diff[i], nextx = now.x + diff[i + 1];
		if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) {
			//まだ見ていない
			que.push(Point{ nexty , nextx });
			dist[nexty][nextx] = dist[now.y][now.x] + 1;
		}
	}
}
cout << dist[G.y][G.x] << endl;

queの中身がこうなってしまいます。

{(b,6)}
->{(b,5),(c,6)}
->{(c,5),(c,5)}//ん?
->{(c,4),(d,5),(c,4),(d,5)}
->{(d,4),(d,4),(d,4),(d,4)}
->{(e,4),(d,3),(e,4),(d,3),(e,4),(d,3),(e,4),(d,3)}//あれ?

このように指数的に増えていってしまうので、TLEしてしまいます。
なぜこのようになるのかというと、
・(b,5)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
・(c,6)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
という動作になってしまっているからです。

これを解消するには、同じものを二回以上見ないように、「そこはもう調べることになっている」という段階で枝狩りしてやります。

struct Point {
	int y, x;
};
char map[100][100];             //HW '.'通行可、'#'通行不可
bool visited[100][100] = {};    //HW 確認したらtrueに
int  dist[100][100];            //HW Sからの距離

que.push(S);
dist[S.y][S.x] = 0; visited[S.y][S.x] = true;
while (!que.empty()) {
	Point now = que.front(); que.pop();
	const int diff[] = { 1,0,-1,0,1 };
	for (int i = 0; i < 4; ++i) {
		int nexty = now.y + diff[i], nextx = now.x + diff[i + 1];
		if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) {
			//まだ見ていない
			que.push(Point{ nexty , nextx });
			dist[nexty][nextx] = dist[now.y][now.x] + 1;
			visited[nexty][nextx] = true;
		}
	}
}
cout << dist[G.y][G.x] << endl;

visitedに代入するタイミングを変えただけですね。