给一个二维的矩阵，包含 'X' 和 'O', 找到所有被 'X' 围绕的区域，并用 'X' 替换其中所有的 'O'。
在线评测地址：
https://www.lintcode.com/problem/surrounded-regions/?utm_source=sc-tianchi-sz0819
样例 1:
输入:
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
样例 2:
输入:
X X X X
X O O X
X O O X
X O X X
输出:
X X X X
X O O X
X O O X
X O X X
【题解】
算法：DFS
思路：先从外围开始，只有身处外围的 O 是无法被包围的，同理，与一个无法被包围的 O 相连的 O 也是无法被包围的。
从外围开始，若遇到边界的 O，则将其标记为 *，意味无法被包围的 O
依次对外圈的“O”的四个方向做DFS，将其可以到达O临时设置为*
最后，遍历数组，
将无法被包围的O，也就是此时被标记为 * 改为 O；
X 不变；
将可以被包围的区域，即没被标记过的O 变为X
复杂度分析
时间复杂度O(n*m)
搜索一次图即可
空间复杂度O(n*m)
图的大小
public class Solution {
/**
* @param board a 2D board containing 'X' and 'O'
* @return void
*/
public void surroundedRegions(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return ;
}
int n = board.length,m = board[0].length;
//四周向中间搜
for (int i = 0; i < n;i++) {
for (int j = 0;j < m;j++) {
if (!is_border(i,j,n,m)) {
continue;
}
if (board[i][j] == 'O') {
dfs(board , i , j);
}
}
}
//遍历图，更新结果
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
else if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
}
public void dfs(char[][] board , int x , int y){
//保证当前点在图中
if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
return ;
}
if (board[x][y] != 'O') {
return ;
}
board[x][y] = '*';
dfs(board , x + 1, y);
dfs(board , x - 1, y);
dfs(board , x , y + 1);
dfs(board , x , y - 1);
}
public boolean is_border(int x,int y,int n,int m) {//判断是否边界
if (x == 0 || y == 0 || x == n - 1||y == m - 1) {
return true;
}
return false;
}}
更多题解参见九章算法官网：
https://www.jiuzhang.com/solution/surrounded-regions/?utm_source=sc-tianchi-sz0819
