题目：Surrounded Regions

给定一个二维矩阵由'x'和'o'表示，其中o被x包围了，如果o上下左右中有其他的o，则被看做是连在一起的，而一起的o中有一个贴边了，就表示这些o都是活的。死的o要替换成x。

思路：

采用广度优先搜索或深度优先搜索来找到连在一起的o；只要遍历过程中有一个贴边的就不在继续搜索，并将现在搜索到的所有活节点全部换成A；

我实际上采用的是广度优先搜索；在搜索过程中未确定的节点我将其转换成了B，最后能判断他的死活时，再转换成对应的标记。

起始外循环是按照从上到下、从左到右的顺序搜索的下面的checkEnclosed函数并不需要再去看它上面的节点或其同一行的右边的点，这些点是判断过得，只有A和X两种可能。

void LeetCode::checkEnclosed(vector
     
      
       >& board, const pair
       
         cur){    bool flag = false;//标记当前检查的一系列节点是否为活节点    queue
        
         
          >Q;    vector
          
           
            > nodes;//候选节点列表 Q.push(cur); while (!Q.empty()){ pair
            
              p = Q.front(); //存在上面的节点，此处在solve应用中不需要，因为是从上到下，从左到右，如果存在上面和左面的节点必然是活节点 if (p.first < cur.first || (p.first == cur.first && p.second < cur.second)){ flag = true; break; } if (!p.first || p.first == board.size() - 1 || !p.second || p.second == board.at(0).size() - 1){ //在边界上，是活节点 flag = true; break;//以确定死活，不再继续搜索 } //死活暂时未知，要看邻接节点的死活 if (board.at(p.first - 1).at(p.second) == 'A'){ flag = true; break; } else if (board.at(p.first - 1).at(p.second) == 'O'){ //存在上边的节点 board.at(p.first - 1).at(p.second) = 'B'; pair
             
              temp(p.first - 1, p.second); Q.push(temp); } if (board.at(p.first).at(p.second + 1) == 'A'){ flag = true; break; } else if (board.at(p.first).at(p.second + 1) == 'O'){ //存在右边的节点 board.at(p.first).at(p.second + 1) = 'B'; pair
              
               temp(p.first, p.second + 1); Q.push(temp); } if (board.at(p.first + 1).at(p.second) == 'A'){ flag = true; break; } else if (board.at(p.first + 1).at(p.second) == 'O'){ //存在下边的节点 board.at(p.first + 1).at(p.second) = 'B'; pair
               
                temp(p.first + 1, p.second); Q.push(temp); } if (board.at(p.first).at(p.second - 1) == 'A'){ flag = true; break; } else if (board.at(p.first).at(p.second - 1) == 'O'){ //存在左边的节点 board.at(p.first).at(p.second - 1) = 'B'; pair
                
                 temp(p.first, p.second - 1); Q.push(temp); } Q.pop(); nodes.push_back(p);//放入候选列表中 } while (!Q.empty()){ //将队列中剩余的节点放到候选列表中 pair
                 
                   p = Q.front(); Q.pop(); nodes.push_back(p); } if (!flag){ //候选列表中的是死节点 auto it = nodes.begin(); while (it != nodes.end()){ board.at((*it).first).at((*it).second) = 'X';//改为死节点 ++it; } } else{ auto it = nodes.begin(); while (it != nodes.end()){ board.at((*it).first).at((*it).second) = 'A';//标记活节点 ++it; } }}void LeetCode::solve(vector
                  
                   
                    >& board){ stack
                    
                     
                      >s; for (vector
                      
                       ::size_type i = 0; i < board.size(); i++){ for (vector
                       
                        ::size_type j = 0; j < board.at(i).size(); j++){ if (board.at(i).at(j) == 'O'){ //需要判断死活的子 pair
                        
                         temp(i, j); checkEnclosed(board, temp); } } } for (vector
                         
                          ::size_type i = 0; i < board.size(); i++){ for (vector
                          
                           ::size_type j = 0; j < board.at(i).size(); j++){ if (board.at(i).at(j) == 'A'){ //用于标记的活节点 board.at(i).at(j) = 'O'; } } }}
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

题目：Number of Islands

给定一个二维矩阵由'1'和'0'表示，其中0表示水，1表示岛屿，上下左右相同表示联通，多个1连成一座岛屿；找岛屿的个数。

思路：

和上面类似，广度优先搜索找到所有与当前节点是一个岛屿的点，并将它们都设为2。

int LeetCode::numIslands(vector
     
      
       >& grid){    int count = 0;    queue
       
        
         >Q;//记录广度优先搜索的节点    for (size_t i = 0; i < grid.size(); ++i){        for (size_t j = 0; j < grid.at(0).size(); ++j){            if (grid.at(i).at(j) == '1'){
   //需要判断是否是岛                ++count;                Q.push(make_pair(i,j));                grid.at(i).at(j) = '2';                while (!Q.empty()){                    auto p = Q.front();                    Q.pop();                    if (p.first > 0 && grid.at(p.first - 1).at(p.second) == '1'){                        Q.push(make_pair(p.first - 1, p.second));//左边                        grid.at(p.first - 1).at(p.second) = '2';//立即设为2，防止重复添加                    }                    if (p.second > 0 && grid.at(p.first).at(p.second - 1) == '1'){                        Q.push(make_pair(p.first, p.second - 1));//上边                        grid.at(p.first).at(p.second - 1) = '2';                    }                    if (p.first < grid.size() - 1 && grid.at(p.first + 1).at(p.second) == '1'){                        Q.push(make_pair(p.first + 1, p.second));//右边                        grid.at(p.first + 1).at(p.second) = '2';                    }                    if (p.second < grid.at(0).size() - 1 && grid.at(p.first).at(p.second + 1) == '1'){                        Q.push(make_pair(p.first, p.second + 1));//下边                        grid.at(p.first).at(p.second + 1) = '2';                    }                }            }        }    }    for (size_t i = 0; i < grid.size(); ++i){        for (size_t j = 0; j < grid.at(0).size(); ++j){            if (grid.at(i).at(j) == '2'){
   //将2还原为1                grid.at(i).at(j) = '1';            }        }    }    return count;}
        
       
      
     

下面是深度优先搜索的实现

int LeetCode::numIslands(vector
     
      
       >& grid){    int count = 0;    stack
       
        
         >s;//记录深度优先搜索的节点    for (size_t i = 0; i < grid.size(); ++i){        for (size_t j = 0; j < grid.at(0).size(); ++j){            if (grid.at(i).at(j) == '1'){
   //需要判断是否是岛                ++count;                s.push(make_pair(i, j));                grid.at(i).at(j) = '2';                while (!s.empty()){                    auto p = s.top();                    if (p.first > 0 && grid.at(p.first - 1).at(p.second) == '1'){                        s.push(make_pair(p.first - 1, p.second));//左边                        grid.at(p.first - 1).at(p.second) = '2';//立即设为2，防止重复添加                    }else if (p.second > 0 && grid.at(p.first).at(p.second - 1) == '1'){                        s.push(make_pair(p.first, p.second - 1));//上边                        grid.at(p.first).at(p.second - 1) = '2';                    }else if (p.first < grid.size() - 1 && grid.at(p.first + 1).at(p.second) == '1'){                        s.push(make_pair(p.first + 1, p.second));//右边                        grid.at(p.first + 1).at(p.second) = '2';                    }else if (p.second < grid.at(0).size() - 1 && grid.at(p.first).at(p.second + 1) == '1'){                        s.push(make_pair(p.first, p.second + 1));//下边                        grid.at(p.first).at(p.second + 1) = '2';                    }                    else{
   //回溯                        s.pop();                    }                }            }        }    }    for (size_t i = 0; i < grid.size(); ++i){        for (size_t j = 0; j < grid.at(0).size(); ++j){            if (grid.at(i).at(j) == '2'){
   //将2还原为1                grid.at(i).at(j) = '1';            }        }    }    return count;}