Leetcode之深度优先搜索（DFS）专题

Leetcode之深度优先搜索（DFS）专题-200. 岛屿数量（Number of Islands）

深度优先搜索的解题详细介绍，点击

1给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
2
3示例 1:
4
5输入:
611110
711010
811000
900000
10
11输出: 1
12示例 2:
13
14输入:
1511000
1611000
1700100
1800011
19
20输出: 3

分析：这题同样是求连通块，相比于130. 被围绕的区域（Surrounded Regions）题少了很多限制条件，同样引入vis，点从其四个方向搜索。

1class Solution {
2    int vis[][] = null;
3    int dirx[] = {0,0,1,-1};
4    int diry[] = {1,-1,0,0};
5    public int numIslands(char[][] grid) {
6        if(grid==null || grid.length==0){
7            return 0;
8        }
9        int ans = 0;
10        vis = new int[grid.length][grid[0].length];
11        
12        for(int i=0;i<grid.length;i++){
13            for(int j=0;j<grid[0].length;j++){
14                if(grid[i][j]=='1' && vis[i][j]!=1){
15                    ans++;
16                    dfs(grid,i,j);
17                }
18            }
19        }
20        return ans;
21    }
22    public void dfs(char[][] board,int x,int y){
23        if(x<0 || y<0 || x>=board.length || y>=board[0].length || board[x][y]=='0' || vis[x][y]==1){
24            return;
25        }
26        vis[x][y] = 1;
27        for(int i=0;i<4;i++){
28            int xx = x+dirx[i];
29            int yy = y+diry[i];
30            dfs(board,xx,yy);
31        }
32        
33        
34    }
35}