首先这当然考的是图的遍历。
其次，这道题是不考虑与边界相连的O的，因此可以在条件判断时加一个是否与边界相连。由于图比较大的情况下，每一个都重新判断会使得重复遍历，因此建立一个visit二维数组，将所有与边界相连通的O全部遍历标记出来，然后再从边界内部的图形开始遍历。
第二，由于大图递归dfs会产生错误，递归深度过深，因此使用队列进行bfs遍历，避免溢出；
第三，对于坐标的存储使用pair较为方便，pair使用方法为，pair<type1,type2> p;进行定义，例如 pair<int,int>。使用p.first,p.second进行访问，（first和second不是方法是属性）。同时 使用make_pair(i,j)这个函数来进行初始化或赋值；
代码如下：
class Solution { public: vector<vector<int> > dirs={{-1,0},{0,-1},{0,1},{1,0}}; void solve(vector<vector<char>>& board) { int m=board.size(); if(m<=2) return; int n=board[0].size(); if(n<=2) return; vector<vector<char> > visit=board; for(int i=0;i<m;i++){ if(visit[i][0]=='O') dfs(visit,i,0); if(visit[i][n-1]=='O') dfs(visit,i,n-1); } for(int j=0;j<n;j++){ if(visit[0][j]=='O') dfs(visit,0,j); if(visit[m-1][j]=='O') dfs(visit,m-1,j); } for(int i=1;i<m-1;i++){ for(int j=1;j<n-1;j++){ if(visit[i][j]=='O') bfs(board,i,j); } } } void dfs(vector<vector<char> >& board,int i,int j){ int m=board.size();int n=board[0].size(); if(i<0 || i>m-1 || j<0 || j>n-1 || board[i][j]!='O') return; board[i][j]='X'; for(auto dir:dirs){ dfs(board,i+dir[0],j+dir[1]); } } void bfs(vector<vector<char> >& board,int i,int j){ int m=board.size();int n=board[0].size(); board[i][j]='X'; queue< pair<int,int> > q; pair<int,int> tmp=make_pair(i,j); q.push(tmp); while(!q.empty()){ pair<int,int> cur=q.front(); q.pop(); board[cur.first][cur.second]='X'; for(auto dir:dirs){ int a=cur.first+dir[0],b=cur.second+dir[0]; if(a<=0 || a>=m-1 || b<=0 || b>=n-1 || board[i][j]!='O') continue; tmp=make_pair(a,b); q.push(tmp); } } } };
时隔多日重新做一遍，采用两个数组，一个是给定的board，另一个是标识边的edges；
首先沿着边初始化edges将与边相连的所有‘O’区域的edges值全部赋值为1；
然后从1~length-1范围内遍历，并对‘O’且非edges的边进行dfs，使其全部变为X；
class Solution { public: vector<vector<int>> dirs={{0,1},{1,0},{0,-1},{-1,0}}; void solve(vector<vector<char>>& board) { int m=board.size(); if(m<=2) return; int n=board[0].size(); if(n<=2) return; //执行step 0： 将与边相连的区域O标识出来 vector<vector<int>> edges(m,vector(n,0)); cout<<m<<endl; cout<<n<<endl; for(int i=0;i<m;i++){ if(board[i][0]=='O' && edges[i][0]==0) dfs(board,edges,i,0,0); if(board[i][n-1]=='O' && edges[i][n-1]==0) dfs(board,edges,i,n-1,0); } for(int j=0;j<n;j++){ if(board[0][j]=='O' && edges[0][j]==0) dfs(board,edges,0,j,0); if(board[m-1][j]=='O' && edges[m-1][j]==0) dfs(board,edges,m-1,j,0); } //执行step1：染色被包围区域； for(int i=1;i<m-1;i++){ for(int j=1;j<n-1;j++){ if(board[i][j]=='O' && edges[i][j]==0) dfs(board,edges,i,j,1); } } } void dfs(vector<vector<char>>& board,vector<vector<int>>& edges,int i,int j,int step){ int m=board.size(),n=board[0].size(); if(i<0 || i>=m || j<0 || j>=n || board[i][j]=='X'|| edges[i][j]==1) return; if(step==0) edges[i][j]=1; if(step==1) board[i][j]='X'; for(auto dir:dirs){ dfs(board,edges,i+dir[0],j+dir[1],step); } } };