https://leetcode.com/contest/weekly-contest-134/problems/escape-a-large-maze/
2次元グリッドがある。
縦も横も10^6である。
通れないマスの集合blockedが与えられる。
始点sourceから終点targetへ隣接するマスを移動して、到達可能か判定せよ。
0≦blocked.size()≦200
前提知識
- 座標圧縮
- BFS
解説
https://leetcode.com/submissions/detail/225447247/
広大なマスがあるが関係するのは、始点と終点とブロックしているマスだけである。
この種類は最大202個なので、このマス以外のマスは縮約して考えることができる。
つまり、座標圧縮をして、小さい盤面に変換しよう。
自分は一応、関係あるマスの縦横1マス分は使うかもと考えて余計に持ってきている。
これでも縦横の最大値は600くらいなので、盤面のサイズ的には大丈夫。
これで始点と終点と移動できないマスがあって、始点から終点への到達可能性判定の問題となった。
これはBFSを使えば効率に判定ができるのでやる。
ちなみに、DFSを使ってやるとStackOverFlowとなったので注意。
#define MAX (1000000-1) int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 }; class Solution { Zaatsu xdic, ydic; void push(int x, int y) { if (0 <= x - 1) xdic.add(x - 1); xdic.add(x); if (x + 1 <= MAX) xdic.add(x + 1); if (0 <= y - 1) ydic.add(y - 1); ydic.add(y); if (y + 1 <= MAX) ydic.add(y + 1); } void convert(int& x, int& y) { x = xdic[x]; y = ydic[y]; } public: bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) { xdic.clear(); ydic.clear(); push(0, 0); push(MAX, MAX); fore(p, blocked) push(p[0], p[1]); push(source[0], source[1]); push(target[0], target[1]); xdic.build(); ydic.build(); fore(p, blocked) convert(p[0], p[1]); convert(source[0], source[1]); convert(target[0], target[1]); int H = ydic.size(); int W = xdic.size(); vector<vector<bool>> visited(H, vector<bool>(W)); vector<vector<bool>> ng(H, vector<bool>(W)); fore(p, blocked) ng[p[1]][p[0]] = true; queue<pair<int, int>> que; que.push({ source[0], source[1] }); visited[source[1]][source[0]] = true; while (!que.empty()) { int x = que.front().first; int y = que.front().second; que.pop(); rep(d, 0, 4) { int xx = x + dx[d]; int yy = y + dy[d]; if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue; if (visited[yy][xx]) continue; if (ng[yy][xx]) continue; if (xx == target[0] and yy == target[1]) return true; que.push({ xx, yy }); visited[yy][xx] = true; } } return false; } };