要点：对遍历到了的格子进行标记。

200. 岛屿数量

题目：200. 岛屿数量
如果不让在原数据上修改，就用visited来记录。

  1. class Solution {
  2.     public int numIslands(char[][] grid) {
  3.       int m=grid.length;
  4.       int n=grid[0].length;
  5.       int count=0;
  6.       for(int i=0;i<m;i++){
  7.         for(int j=0;j<n;j++){
  8.           if(grid[i][j]=='1'){
  9.             count++;
  10.             dfs(i,j,grid);
  11.           }
  12.         }
  13.       }
  14.       return count;
  15.     }
  17.     private void dfs(int i,int j,char[][] grid){
  18.       int m=grid.length;
  19.       int n=grid[0].length;
  20.       if(i>=0&&j>=0&&i<m&&j<n&&grid[i][j]=='1'){
  21.         grid[i][j]='0';
  22.         dfs(i+1,j,grid);
  23.         dfs(i-1,j,grid);
  24.         dfs(i,j+1,grid);
  25.         dfs(i,j-1,grid);
  26.       }
  27.     }
  28. }

695. 岛屿的最大面积

题目：695. 岛屿的最大面积

  1. class Solution {
  2.     public int maxAreaOfIsland(int[][] grid) {
  3.       if(grid==null||grid.length==0) return 0;
  4.       int m=grid.length;
  5.       int n=grid[0].length;
  6.       int maxArea=0;
  7.       for(int i=0;i<m;i++){
  8.         for(int j=0;j<n;j++){
  9.           maxArea=Math.max(maxArea,dfs(grid,i,j));
  10.         }
  11.       }
  12.       return maxArea;
  13.     }
  15.     private int dfs(int[][] grid,int i,int j){
  16.       if(grid==null||grid.length==0) return 0;
  17.       int m=grid.length;
  18.       int n=grid[0].length;
  19.       if(i<0||j<0||i>=m||j>=n||grid[i][j]==0){
  20.         return 0;
  21.       }
  22.       int area=1;
  23.       grid[i][j]=0;
  24.       area+=dfs(grid,i+1,j);
  25.       area+=dfs(grid,i-1,j);
  26.       area+=dfs(grid,i,j+1);
  27.       area+=dfs(grid,i,j-1);
  28.       return area;
  29.     }
  30. }

130. 被围绕的区域

题目：130. 被围绕的区域

  1. class Solution {
  2.     public void solve(char[][] board) {
  3.       int m=board.length;
  4.       int n=board[0].length;
  5.       for(int i=0;i<m;i++){
  6.         if(board[i][0]=='O') dfs(board, i, 0);
  7.         if(board[i][n-1]=='O') dfs(board, i, n-1);
  8.       }
  9.       for(int j=0;j<n;j++){
  10.         if(board[0][j]=='O') dfs(board, 0, j);
  11.         if(board[m-1][j]=='O') dfs(board, m-1, j);
  12.       }
  13.       for(int i=0;i<m;i++){
  14.         for(int j=0;j<n;j++){
  15.           if(board[i][j]=='O') board[i][j]='X';
  16.           if(board[i][j]=='#') board[i][j]='O';
  17.         }
  18.       }
  19.     }
  21.     private void dfs(char[][] board,int i,int j){
  22.       int m=board.length;
  23.       int n=board[0].length;
  24.       if(i<0||j<0||i>=m||j>=n||board[i][j]!='O') return;
  25.       board[i][j]='#';
  26.       dfs(board, i+1, j);
  27.       dfs(board, i-1, j);
  28.       dfs(board, i, j+1);
  29.       dfs(board, i, j-1);
  30.     }
  31. }