130. Surrounded Regions

题目

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 XX O O XX X O XX O X XAfter running your function, the board should be:X X X XX X X XX X X XX O X X

解析

• 核心思想：只有边界上'O'的位置组成的片区不会被'X'包围。因此先对边界上的'O'遍历之后暂存为''。非''的'O'即被'X'包围了。

• 此题考查DFS/BFS的思想，就像走迷宫问题，入口和出口位置不同，DFS/BFS的效率不一样，递归式的DFS 会出现stackoverflow 或者run time的问题

• bug :发现leetcode系统必须检查输入为空的情况！否则出现"Runtime Error Message:reference binding to null pointer of type 'struct value_type' Last executed input: [] 之类的错误！！！

class Solution {public:    void bfs(vector
    
     
      > &board,int cur_i,int cur_j,int row,int col)    {        if(board[cur_i][cur_j]!='O')            return;        board[cur_i][cur_j]='*';        queue
      
       
        > q;        q.push(make_pair(cur_i,cur_j));                while(!q.empty())        {            int i=q.front().first;            int j=q.front().second;            q.pop();            //board[i][j]='*';            if(i-1>=0&&board[i-1][j]=='O')            {                board[i-1][j]='*';                q.push(make_pair(i-1,j));            }            if(i+1
        
         =0&&board[i][j-1]=='O')            {                board[i][j-1]='*';                q.push(make_pair(i,j-1));                            }            if(j+1
         
          > &board) { //bfs if (board.empty()) //bug :发现leetcode系统必须检查输入为空的情况！ return; int row=board.size(); int col=board[0].size(); if(row==0||col==0) return; for(int i=0;i
         
        
       
      
     
    

• 这样考虑时间复杂度

for(int i=0;i

题目来源