1036. 逃离大迷宫
在一个 106 x 106 的网格中，每个网格上方格的坐标为 (x, y) 。
现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。
只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/escape-a-large-maze
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
常规广度搜索（超时）
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
class Solution {
private static final int LIMIT = 1000000;
private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private long hash(int[] data) {
return (long) data[0] * (LIMIT + 1) + data[1];
}
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
Set visited = new HashSet<>();
for (int[] block : blocked) {
visited.add(hash(block));
}
if (visited.contains(hash(source)) || visited.contains(hash(target))) {
return false;
}
Queue queue = new LinkedList<>();
queue.offer(source);
visited.add(hash(source));
while (!queue.isEmpty()) {
int[] node = queue.poll();
if (node[0] == target[0] && node[1] == target[1]) {
return true;
}
for (int i = 0; i < directions.length; ++i) {
int x = node[0] + directions[i][0];
int y = node[1] + directions[i][1];
long h = hash(new int[]{x, y});
if (x >= 0 && x < LIMIT && y >= 0 && y < LIMIT && !visited.contains(h)) {
queue.offer(new int[]{x, y});
visited.add(h);
}
}
}
return false;
}
}
有限步数
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
class Solution {
// 在包围圈中
static final int BLOCKED = -1;
// 不在包围圈中
static final int VALID = 0;
// 无论在不在包围圈中，但在 n(n-1)/2 步搜索的过程中经过了 target
static final int FOUND = 1;
static final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static final int BOUNDARY = 1000000;
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
if (blocked.length < 2) {
return true;
}
Set hashBlocked = new HashSet();
for (int[] pos : blocked) {
hashBlocked.add(new Pair(pos[0], pos[1]));
}
int result = check(blocked, source, target, hashBlocked);
if (result == FOUND) {
return true;
} else if (result == BLOCKED) {
return false;
} else {
result = check(blocked, target, source, hashBlocked);
return result != BLOCKED;
}
}
public int check(int[][] blocked, int[] start, int[] finish, Set hashBlocked) {
int sx = start[0], sy = start[1];
int fx = finish[0], fy = finish[1];
int countdown = blocked.length * (blocked.length - 1) / 2;
Pair startPair = new Pair(sx, sy);
Pair endPair = new Pair(fx, fy);
Queue queue = new ArrayDeque();
queue.offer(startPair);
Set visited = new HashSet();
visited.add(startPair);
while (!queue.isEmpty() && countdown > 0) {
Pair pair = queue.poll();
if (pair.equals(endPair)) {
return FOUND;
}
int x = pair.x, y = pair.y;
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d][0], ny = y + dirs[d][1];
Pair newPair = new Pair(nx, ny);
if (nx >= 0 && nx < BOUNDARY && ny >= 0 && ny < BOUNDARY && !hashBlocked.contains(newPair) && !visited.contains(newPair)) {
--countdown;
queue.offer(newPair);
visited.add(newPair);
}
}
}
if (countdown > 0) {
return BLOCKED;
}
return VALID;
}
}
class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int hashCode() {
return (int) ((long) x << 20 | y);
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Pair) {
Pair pair2 = (Pair) obj;
return x == pair2.x && y == pair2.y;
}
return false;
}
}
离散化
import java.util.*;
class Solution {
static final int BOUNDARY = 1000000;
static final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
if (blocked.length < 2) {
return true;
}
// 离散化
TreeSet rows = new TreeSet<>();
TreeSet columns = new TreeSet<>();
for (int[] pos : blocked) {
rows.add(pos[0]);
columns.add(pos[1]);
}
rows.add(source[0]);
rows.add(target[0]);
columns.add(source[1]);
columns.add(target[1]);
Map rMapping = new HashMap<>();
Map cMapping = new HashMap<>();
int firstRow = rows.first();
int rId = (firstRow == 0 ? 0 : 1);
rMapping.put(firstRow, rId);
int prevRow = firstRow;
for (int row : rows) {
if (row == firstRow) {
continue;
}
rId += (row == prevRow + 1 ? 1 : 2);
rMapping.put(row, rId);
prevRow = row;
}
if (prevRow != BOUNDARY - 1) {
++rId;
}
int firstColumn = columns.first();
int cId = (firstColumn == 0 ? 0 : 1);
cMapping.put(firstColumn, cId);
int prevColumn = firstColumn;
for (int column : columns) {
if (column == firstColumn) {
continue;
}
cId += (column == prevColumn + 1 ? 1 : 2);
cMapping.put(column, cId);
prevColumn = column;
}
if (prevColumn != BOUNDARY - 1) {
++cId;
}
int[][] grid = new int[rId + 1][cId + 1];
for (int[] pos : blocked) {
int x = pos[0], y = pos[1];
grid[rMapping.get(x)][cMapping.get(y)] = 1;
}
int sx = rMapping.get(source[0]), sy = cMapping.get(source[1]);
int tx = rMapping.get(target[0]), ty = cMapping.get(target[1]);
Queue queue = new LinkedList<>();
queue.offer(new int[]{sx, sy});
grid[sx][sy] = 1;
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int x = arr[0], y = arr[1];
if (x == tx && y == ty) {
return true;
}
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d][0], ny = y + dirs[d][1];
if (nx >= 0 && nx <= rId && ny >= 0 && ny <= cId && grid[nx][ny] != 1) {
queue.offer(new int[]{nx, ny});
grid[nx][ny] = 1;
}
}
}
return false;
}
}