被包围的岛屿_岛屿数量

被围绕的区域

被围绕的区域

//这里我们采用逆向思维,我们可以找到没有被x全部环绕的O 然后对O进行深度遍历!
//标记后,得到新的矩阵,再将所以的O修改成X 再将刚刚标记的改成O!
class Solution {
    int[][] next = {{1,0},{-1,0},{0,1},{0,-1}};
    public void DSF(char[][] board,int row,int col,int sr,int sc){
         //用Z标记该位置
         board[sr][sc]='Z';
          for(int i = 0;i<next.length;i++){
                int x = sr + next[i][0];
                int y = sc + next[i][1];
                if(x>=row||x<0||y>=col||y<0){
                    //越界
                    continue;
                }
                if(board[x][y]=='O'){
                    //深度遍历
                    DSF(board,row,col,x,y);
                }
          }
    }
    public void solve(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        //先找边界的O深度遍历修改!
        for(int i = 0;i<row;i++){
            //左右边界!
            if(board[i][0]=='O'){//左边
                DSF(board,row,col,i,0);
            }
             if(board[i][col-1]=='O'){//右边
                DSF(board,row,col,i,col-1);
            }
        }
        for(int i = 1;i<col-1;i++){
            //上下边界!
            if(board[0][i]=='O'){//上边
                DSF(board,row,col,0,i);
            }
             if(board[row-1][i]=='O'){//下边
                DSF(board,row,col,row-1,i);
            }
        }
        //遍历将围绕的O修改成X,标记的改为O!
        for(int i = 0;i<row;i++){
            for(int j = 0;j<col;j++){
                if(board[i][j]=='O'){//修改O
                    board[i][j]='X';
                }
                if(board[i][j]=='Z'){//修改标记
                    board[i][j]='O';
                }
            }
        }  
    }
}

岛屿数量

岛屿数量

class Solution {
    int[][] next = {{1,0},{-1,0},{0,1},{0,-1}};
    public void DSF(char[][] board,int row,int col,int sr,int sc){
         //用'2'标记该位置
         board[sr][sc]='2';
          for(int i = 0;i<next.length;i++){
                int x = sr + next[i][0];
                int y = sc + next[i][1];
                if(x>=row||x<0||y>=col||y<0){
                    //越界
                    continue;
                }
                if(board[x][y]=='1'){
                    //深度遍历
                    DSF(board,row,col,x,y);
                }
          }
    }
    public int numIslands(char[][] grid) {
         int result = 0;
         int row = grid.length;
         int col = grid[0].length;
         for(int i = 0;i<row;i++){
             for(int j = 0;j<col;j++){
                 if(grid[i][j]=='1'){//标记!
                     DSF(grid,row,col,i,j);
                     result++;
                 }
             } 
         }
         return result;
    }
}