note-java-bfs:surrounded-regions

题目

被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

class Solution {
    int rows,cols;
    public void solve(char[][] board) {
          rows=board.length;
          cols=board[0].length;
        //  if(rows==0) return ;
        //  //dfs
        //  for(int i=0;i<cols;i++){
        //      dfs(0,i,board);
        //      dfs(rows-1,i,board);
        //  }
        //  for(int j=1;j<rows-1;j++){
        //      dfs(j,0,board);
        //      dfs(j,cols-1,board);
        //  }
        //   for(int i=0;i<rows;i++){
        //       for(int j=0;j<cols;j++){
        //           if(board[i][j]=='V') 
        //           board[i][j] ='O';
        //           else if(board[i][j]== 'O')
        //           board[i][j]='X';
        //       }
        //   }  

         bfs(board);   

    }
    
    void bfs(char[][] board){
        Queue<int[]> queue=new LinkedList<int[]>();

         for(int i=0;i<cols;i++){
                 if(board[0][i]=='O'){
                     queue.offer(new int[]{0,i});
                     board[0][i]='V'; 
                 }
                 if(board[rows-1][i]=='O'){
                     queue.offer(new int[]{rows-1,i});  
                     board[rows-1][i]='V';
                 }
                    
         }
         for(int j=1;j<rows-1;j++){

                if(board[j][0]=='O'){
                     queue.offer(new int[]{j,0});
                     board[j][0]='V';
                }
                if(board[j][cols-1]=='O'){
                     queue.offer(new int[]{j,cols-1});
                     board[j][cols-1]='V';
                }

                
         }
         int[][] dirs={
             {0,1},
             {0,-1},
             {1,0},
             {-1,0}
         };
         while(!queue.isEmpty()){
               int[] node=queue.poll();
               int x=node[0],y=node[1];
               for(int i=0;i<4;i++){
                    int xP=dirs[i][0],yP=dirs[i][1];
                    if(x+xP<=0||x+xP>=rows||y+yP<=0||y+yP>=cols||board[x+xP][y+yP]!='O')
                     continue;
                    queue.offer(new int[]{x+xP,y+yP});
                    board[x+xP][y+yP]='V';
               }
         }
          for(int i=0;i<rows;i++){
              for(int j=0;j<cols;j++){
                  if(board[i][j]=='V') 
                  board[i][j] ='O';
                  else if(board[i][j]== 'O')
                  board[i][j]='X';
              }
          }  
    }
    void dfs(int row,int col,char[][] board){
            if(row<0||row>=rows||col<0||col>=cols||board[row][col]!= 'O') return;
            board[row][col]='V';
            dfs(row+1,col,board);
            dfs(row-1,col,board);
            dfs(row,col+1,board);
            dfs(row,col-1,board);

    }
}

最后

以上就是灵巧钢笔为你收集整理的note-java-bfs:surrounded-regions的全部内容，希望文章能够帮你解决note-java-bfs:surrounded-regions所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。