題目鏈接
https://leetcode-cn.com/problems/surrounded-regions/
題目描述
給定一個二維的矩陣睁本，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 圍繞的區(qū)域逃默，并將這些區(qū)域里所有的 'O' 用 'X' 填充虾宇。
示例:
X X X X
X O O X
X X O X
X O X X
運(yùn)行你的函數(shù)后搓彻，矩陣變?yōu)椋?br> X X X X
X X X X
X X X X
X O X X
題解
題目意思就是只要被X所包圍的地方將被吃掉，就像下圍棋一樣嘱朽，而在邊緣的O相當(dāng)于圍三缺一實(shí)際上是一片活棋也就保留了下來旭贬。
于是我們只要找出所有與四邊所在的O以及與其相連的O標(biā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);
}
}
}
結(jié)果
image.png
