Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
For example, X X X X X O O X X X O X X O X X After running your function, the board should be:
X X X X X X X X X X X X X O X X
这道题一直过不去… 网上的dfs代码是过不去的，最新的用例似乎加强了数据。 用BFS的话，无论我申明了struct或者是使用pair，全部超内存。。。 唯一一个过了的是使用c++的Lamda表达式的，这个可以提升效率？ 有哪路大神知道的话给指点指点。
class Solution { public: struct Pos{ int x,y; Pos(int vx,int vy) : x(vx), y(vy) {} }; //四个方向 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int m,n;//矩阵大小 void solve(vector<vector<char> >& board) { this->m=board.size(); if(m==0) return; this->n=board[0].size(); for(int i=0;i<m;i++){ if(board[i][0]=='O') dfs(i,0,board); if(board[i][n-1]=='O') dfs(i,n-1,board); } for(int i=0;i<n;i++){ if(board[0][i]=='O') dfs(0,i,board); if(board[m-1][i]=='O') dfs(m-1,i,board); } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='O') board[i][j]='X'; else if(board[i][j]=='+') board[i][j]='O'; } } } void dfs(int x,int y,vector<vector<char> >& board){ int i=x,j=y; if(board[i][j]=='O'){ board[i][j]='+'; for(int i=0;i<4;i++){ int next_x=x+dir[i][0]; int next_y=y+dir[i][1]; //越界 if(next_x<0 || next_x>=m || next_y<0 ||next_y>=n) continue; dfs(next_x,next_y,board); } } } //通过bfs,从x行y列开始寻找能否走出迷宫 void bfs(int x,int y,vector<vector<char> >& board){ // int visit[m][n]; // memset(visit,0,sizeof(visit)); queue<Pos*> Q; Pos *p=new Pos(x,y); Q.push(p); while(!Q.empty()){ Pos *p=Q.front(); Q.pop(); board[p->x][p->y]='+'; //如果type为1，表示要填充所有遍历到的节点为X // if(type==1) board[p->x][p->y]='X'; // else{ //判断是否是边界 // if(p->x==0 || p->y==0 || p->x==m-1 || p->y==n-1){ // flag=true; // // return true; // } // } for(int i=0;i<4;i++){ int next_x=p->x+dir[i][0]; int next_y=p->y+dir[i][1]; //越界 if(next_x<0 || next_x>=m || next_y<0 ||next_y>=n) continue; //判重 // if(visit[next_x][next_y]) continue; //只能走O if(board[next_x][next_y]!='O') continue; // printf("pos %d %d\n",) //符合条件推入队列 // visit[next_x][next_y]=1; Q.push(new Pos(next_x,next_y)); } } // //如果flag=true表明Q2里的节点都是与边界相连的 // //为false表示从当前一点不能到达边界，应当全部置为X // if(!flag){ // while(!Q2.empty()){ // Pos *p=Q2.front(); // Q2.pop(); // board[p->x][p->y]='X'; // } // } // return false; } /* void solve(vector<vector<char> >& board) { this->m=board.size(); if(m==0) return; this->n=board[0].size(); for(int i=0;i<m;i++){ if(board[i][0]=='O') bfs(i,0,board); if(board[i][n-1]=='O') bfs(i,n-1,board); } for(int i=0;i<n;i++){ if(board[0][i]=='O') bfs(0,i,board); if(board[m-1][i]=='O') bfs(m-1,i,board); } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='O') board[i][j]='X'; else if(board[i][j]=='+') board[i][j]='O'; } } // //遍历整个面板 // for(int i=0;i<m;i++){ // for(int j=0;j<n;j++){ // //如果找到一个O // //则需要判断这个O是否被X包围 // //被X包围的标志是从该点出发，无法到达迷宫边缘 // // if(board[i][j]=='O'){ // // //判断是否被包围 true表示没有被包围 // // if(!bfs(i,j,board,0)){ // // // printf("pos %d %d\n",i,j); // // //表示bfs没有走到边界的地方 // // //那么这些区域应当被填充上X // // bfs(i,j,board,1); // // } // // } // if(board[i][j]=='O') // bfs(i,j,board); // } // } // for(int i=0;i<m;i++){ // for(int j=0;j<n;j++){ // if(board[i][j]=='+') // board[i][j]='O'; // } // } }*/ };