一、题目
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’
二、思路
逆向思维：要把被X包围的所有O，都替换为X，就可以先把没被X包围的O找出来（这些O最后结果不会改变），可以通过遍历边界上的O，对其进行dfs找到这些O的连通分量。
你肯定会问，会不会有存在不是上面情况，并且没被X包围的呀——不存在的，不在边界O的连通分量，那自然是在“内部”了，即被X包围。
（1）从边界出发，先把边界上和O连通点找到，把这些变成A；
（2）然后遍历整个board把O变成X, 把B变成O。
三、代码
class Solution { private: vector<pair<int,int>>directions{{0,1},{0,-1},{1,0},{-1,0}}; public: void solve(vector<vector<char>>& board) { int row=board.size();//row行数 int col=board[0].size();//column列数 for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(board[i][j]=='O' && (i == row-1 || j == col-1 || i == 0 || j == 0)){ dfs(board,i,j); } } } for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(board[i][j] == 'A'){ board[i][j] = 'O'; }else if(board[i][j] == 'O'){ board[i][j] = 'X'; } } } } void dfs(vector<vector<char>>&board,int x,int y){ if(!isarea(board,x,y)){ return;//如果坐标(x,y)超过网格范围，则直接返回 } if(board[x][y]!='O'){ return;//如果不是岛屿(1)则直接返回 } board[x][y]='A';//将格子标记为已遍历过,重新淹水 for(auto dir:directions){ int newx=x+dir.first,newy=y+dir.second; if(isarea(board,newx,newy)){//在网格范围内(正常) //board[x][y]='X'; dfs(board,newx,newy); } } } bool isarea(vector<vector<char>>&board,int x,int y){//判断点是否在网格内 if(x>=0 && x<board.size() && 0<=y && y<board[0].size()){ return true; }else{ return false; } } };
