Escape a Large Maze [LeetCode 1036]

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;
	}
};