本文主要是介绍算法——矩阵，被围绕的区域，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
. - 力扣（LeetCode）
最开始也是考虑使用dfs，对于矩阵中的每个点，如果能到达边界的O，则跳过继续dfs。否则如果上下左右四个方向都无法到达边界的O，则说明当前的无法到达，在一个set中记录他的行数列数。
最后对每个记录的点标记为X即可。
但是有问题，首先可能会出现永久递归无法跳出来。如果使用父节点记录当前节点的前一个节点，则如果父节点恰好通往边界O,会导致错误。使用visited来记录状态也不行。
应该反向思维，从每个边界O出发dfs。
思路：对于边界上的每一个点进行dfs。如果当前点为X则直接跳过。如果当前点为O,则把O该为A，继续dfs。
使用A来记录从边界上的O所能够到达的点。
遍历完之后，再把矩阵中的O改为X,表示未与边界O相连。把矩阵中的A该为O，表示与边界相连的O，不变。
注意dfs函数中，如果发现不是X不能直接else，而要判断是不是为O，为O才继续dfs。
如果不这样的话当前为A也会继续dfs，导致永远无法停止的递归。
class Solution {
public:void dfs(vector<vector<char>>& board,int row,int col){if(board[row][col]=='X')return;else if(board[row][col]=='O'){board[row][col]='A';if(row>0)dfs(board,row-1,col);if(row<board.size()-1)dfs(board,row+1,col);if(col>0)dfs(board,row,col-1);if(col<board[0].size()-1)dfs(board,row,col+1);}}void solve(vector<vector<char>>& board) {for(int i=0;i<board.size();i++){dfs(board,i,0);dfs(board,i,board[0].size()-1);}for(int i=1;i<board[0].size()-1;i++){dfs(board,0,i);dfs(board,board.size()-1,i);}for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){if(board[i][j]=='O')board[i][j]='X';else if(board[i][j]=='A')board[i][j]='O';}}}
};这篇关于算法——矩阵，被围绕的区域的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
