给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
官方题解从边界向内扩展更简单
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
class Solution {
private int[] dx = {0, 1, 0, -1};
private int[] dy = {1, 0, -1, 0};
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
Map<Character, Boolean> ok = new HashMap<>();
int n = board.length, m = board[0].length;
char idx = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (board[i][j] == 'O') {
idx++;
LinkedList<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
board[i][j] = idx;
boolean isOk = true;
while (!queue.isEmpty()) {
int[] node = queue.poll();
for (int k = 0; k < 4; ++k) {
int x = dx[k] + node[0];
int y = dy[k] + node[1];
if (x < 0 || x >= n || y < 0 || y >= m) {
isOk = false;
} else if (board[x][y] == 'O') {
queue.offer(new int[]{x, y});
board[x][y] = idx;
}
}
}
ok.put(idx, isOk);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (ok.containsKey(board[i][j])) {
if (ok.get(board[i][j])) {
board[i][j] = 'X';
} else {
board[i][j] = 'O';
}
}
}
}
}
}