幅優先探索の一般的な罠
幅優先探索で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に代入するタイミングを変えただけですね。