[LeetCode]Surrounded Regions-白红宇

[LeetCode]Surrounded Regions

阅读量：4151 次

发布时间：2019-05-25

本文共 2614 字，大约阅读时间需要 8 分钟。

class Solution {public:	vector
   
    
     > BFS(int curX, int curY, vector
     
      
       > &board, vector
       
        
         >& visited, bool& bFilp) { int n = board.size(); int m = board[0].size(); int dir[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0}}; queue
         
          
           > q; visited[curX][curY] = true; q.push(make_pair(curX, curY)); vector
           
            
             > path; while (!q.empty()) { int x = q.front().first; int y = q.front().second; path.push_back(q.front()); q.pop(); for (int i = 0; i < 4; ++i) { int nextX = x+dir[i][0]; int nextY = y+dir[i][1]; if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) { if(!visited[nextX][nextY] && board[nextX][nextY] == 'O') { q.push(make_pair(nextX, nextY)); visited[nextX][nextY] = true; } } else bFilp = false; } } return path; } void solve(vector
             
              
               > &board) { // Start typing your C/C++ solution below // DO NOT write int main() function int n = board.size(); if(n == 0) return; int m = board[0].size(); vector
               
                
                 > visited; visited.resize(n); for(int i = 0; i < n; ++i) visited[i].assign(m, false); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if(!visited[i][j] && board[i][j] == 'O') { bool bFlip = true; vector
                 
                  
                   > path = BFS(i, j, board, visited, bFlip); if(bFlip) { for (int pIdx = 0; pIdx < path.size(); ++pIdx) board[path[pIdx].first][path[pIdx].second] = 'X'; } } } } }};

second time

class Solution {public:    int dir[4][2] = {
  {0,1},{0,-1},{1,0},{-1,0}};    void solveUtil(vector
   
    
      >& board, vector
     
      
        >& visited, int ix, int iy, vector
       
        
          >& curPath, bool& isSurrounded) { int n = board.size(); int m = board[0].size(); queue
         
          
            > posQ; posQ.push(pair
           
            (ix, iy)); while(!posQ.empty()) { int curX = posQ.front().first; int curY = posQ.front().second; posQ.pop(); if(board[curX][curY] == 'O' && !visited[curX][curY]) { curPath.push_back(pair
            
             (curX, curY)); visited[curX][curY] = true; for(int k = 0; k < 4; ++k) { int newX = curX+dir[k][0]; int newY = curY+dir[k][1]; if(newX < 0 || newX >= n || newY < 0 || newY >= m) isSurrounded = false; else if (!visited[newX][newY]) posQ.push(pair
             
              (newX, newY)); } } } } void solve(vector
              
               
                > &board) { // Start typing your C/C++ solution below // DO NOT write int main() function int n = board.size(); if(n == 0) return; int m = board[0].size(); vector
                
                 
                   > visited(n, vector
                  
                   (m, false)); for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { vector
                   
                    
                      > curPath; bool isSurrounded = true; if(!visited[i][j]) solveUtil(board, visited, i, j, curPath, isSurrounded); if(isSurrounded) { for(int i = 0; i < curPath.size(); ++i) board[curPath[i].first][curPath[i].second] = 'X'; } } } }};