题目链接
https://leetcode-cn.com/problems/surrounded-regions/
题目描述
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
题解
题目意思就是只要被X所包围的地方将被吃掉，就像下围棋一样，而在边缘的O相当于围三缺一实际上是一片活棋也就保留了下来。
于是我们只要找出所有与四边所在的O以及与其相连的O标记为任意字符，剩余O皆是被X所包围的，也就是会被X填充
代码
public void solve(char[][] board) {
int length = board.length;
if (length == 0)
return;
int rowLength = board[0].length;
for (int i = 0; i < length; i++) {
if (board[i][0] == 'O') {
dfs(i, 0, board);
}
if (board[i][rowLength - 1] == 'O') {
dfs(i, rowLength - 1, board);
}
}
for (int i = 0; i < rowLength; i++) {
if (board[0][i] == 'O') {
dfs(0, i, board);
}
if (board[length - 1][i] == 'O') {
dfs(length - 1, i, board);
}
}
for (int i = 0; i < length; i++) {
for (int j = 0; j < rowLength; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == 'Y')
board[i][j] = 'O';
}
}
}
public void dfs(int x, int y, char[][] map) {
if (x >= 0 && x < map.length && y >= 0 && y < map[0].length) {
if (map[x][y] == 'O') {
map[x][y] = 'Y';
dfs(x - 1, y, map);
dfs(x + 1, y, map);
dfs(x, y - 1, map);
dfs(x, y + 1, map);
}
}
}
结果
image.png
