棋盘类问题有一些难度，繁琐抽象，但我觉得一般能够bug-free的快速做出就可以达到hire甚至strong hire的水平。在公司面试中也容易出现，所以要认真啃。
130. Surrounded Regions
非常喜欢这道题。
棋盘类问题的经典，BFS和union-find都可以解，这里先说BFS。
这道题O就像是盆地，X是平原，我们要做的就是向平原包围的盆地注水，然后把盆地填平。
所以遇到连通的盆地的时候，需要用到BFS来全部注水，找到所有盆地。
这题用到的变量比较多，很多地方需要小心处理，变量和下标有时比较麻烦会出错，理解又抽象，这是棋盘类的特点。
这题当然也可以用 Union-Find 写，先把所有最外圈的 boundry 连上，然后把里面的相邻 'O' 做 union，最后扫矩阵的时候，如果对应的 root 不是 boundry root 就留下，不然都改成 'X'.
不过只是在这个问题上，不是很简洁。
public class Solution {
int m, n;
int No;
public void solve(char[][] board) {
m = board.length;
if (m == 0) return;
n = board[0].length;
int[][] mark = new int[m][n];
boolean[] surrounded = new boolean[m * n + 1];
Arrays.fill(surrounded, true);
No = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O' && mark[i][j] == 0) {
No++;
bfs(i, j, board, mark, surrounded);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O' && surrounded[mark[i][j]]) {
board[i][j] = 'X';
}
}
}
}
private void bfs(int sx, int sy, char[][] board, int[][] mark, boolean[] surrounded) {
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
Queue<Integer> qx = new LinkedList<>();
Queue<Integer> qy = new LinkedList<>();
qx.offer(sx);
qy.offer(sy);
mark[sx][sy] = No;
while (!qx.isEmpty()) {
int ox = qx.poll();
int oy = qy.poll();
if (ox == 0 || ox == m - 1 || oy == 0 || oy == n - 1) {
surrounded[No] = false;
}
for (int i = 0; i < 4; ++i) {
int nx = ox + dx[i];
int ny = oy + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
mark[nx][ny] == 0 && board[nx][ny] == 'O') {
mark[nx][ny] = No;
qx.offer(nx);
qy.offer(ny);
}
}
}
}
}
286. Walls and Gates
- [0 , INF, 0, INF, INF]
- [-1, -1 , 0 , -1 , INF]
- [-1 , 0 , 0 , 0 , INF]
- [-1 , INF , 0 , 0 , -1]
INF 空房
-1 墙
0 门
目标是找最近的门，门到房间最短的距离，用BFS。问题在于我们有好几个门，顺着上一道题的思路，本来应该从一个门开始“注水”，在很多个门的情况下，要想所有的门同时开始注水，就需要一个抽象的“超级门”，这个超级源点dummy连结了所有的门，问题就变成了从dummy到所有的房间的最短距离。
空房间是盆地，墙是平原，门是注水点。
和上一题的代码几乎一样，只不过有了好几个门之后，我们首先要把所有源点放入queue中，计算距离的时候只需要加一句比前一个位置上更远了单位1距离就行了，到达不了的点在输入的时候题目相当于已经帮我们解决了，所以不用担心。
public class Solution {
static final int INF = Integer.MAX_VALUE;
public void wallsAndGates(int[][] rooms) {
int m = rooms.length;
if (m == 0) {
return;
}
int n = rooms[0].length;
int[] dx = {1, 0, -1, 0};
int[] dy = {0, -1, 0, 1};
Queue<Integer> qx = new LinkedList<>();
Queue<Integer> qy = new LinkedList<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (rooms[i][j] == 0) {
qx.offer(i);
qy.offer(j);
}
}
}
while (!qx.isEmpty()) {
int ox = qx.poll();
int oy = qy.poll();
for (int i = 0; i < 4; ++i) {
int nx = ox + dx[i];
int ny = oy + dy[i];
if (nx < m && nx >= 0 && ny < n && ny >= 0
&& rooms[nx][ny] == INF) {
qx.offer(nx);
qy.offer(ny);
rooms[nx][ny] = rooms[ox][oy] + 1;
}
}
}
}
}
675. Cut Off Trees for Golf Event
挺综合的一道题，就好像高考数学倒数第二道大题一样，考察很综合，pq + bfs，word ladder + maze + sort。做完感觉复习了好几道题。
class Solution {
int[] dx = new int[]{1,0,-1,0};
int[] dy = new int[]{0,-1,0,1};
public int cutOffTree(List<List<Integer>> forest) {
if (forest == null || forest.size() == 0) return -1;
int m = forest.size();
int n = forest.get(0).size();
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
return a[2] - b[2];
}
});
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (forest.get(i).get(j) == 0) continue;
pq.add(new int[]{i, j, forest.get(i).get(j)});
}
}
int[] start = new int[2];
int result = 0;
while (!pq.isEmpty()) {
int[] node = pq.poll();
int[] tree = new int[]{node[0], node[1]};
int step = bfs(start, tree, forest);
if (step < 0) return -1;
result += step;
start[0] = tree[0];
start[1] = tree[1];
}
return result;
}
private int bfs(int[] start, int[] end, List<List<Integer>> forest) {
int m = forest.size();
int n = forest.get(0).size();
int step = 0;
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
boolean[][] visited = new boolean[m][n];
visited[start[0]][start[1]] = true;
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; ++k) {
int[] node = queue.poll();
if (node[0] == end[0] && node[1] == end[1]) return step;
for (int i = 0; i < 4; ++i) {
int newX = node[0] + dx[i];
int newY = node[1] + dy[i];
if (newX >= 0 && newX < m && newY >= 0 && newY < n &&
!visited[newX][newY] && forest.get(newX).get(newY) != 0) {
queue.offer(new int[]{newX, newY});
visited[newX][newY] = true;
}
}
}
step++;
}
return -1;
}
}