leetcode:【深度优先搜索】Number of Islands

| 分类 算法  | 标签 leetcode  dfs 

问题描述

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:  
11110  
11010  
11000  
00000  
Answer: 1  

Example 2:  
11000  
11000  
00100  
00011  
Answer: 3

code

//如果是弄个visited[][]就是stack over flow,直接将grid[i][j]='0'
public class Solution {
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int count = 0;
        for(int i = 0;i<grid.length;i++) 
            for(int j = 0;j<grid[0].length;j++) {
                if(grid[i][j] == '1') {
                    count++;
                    dfs(grid,i,j);
                }
            }
        return count;
    }
    private void dfs(char[][] grid,int i,int j) {
        if(i <0 || i>=grid.length || j <0 || j>=grid[0].length || grid[i][j] == '0')
            return;
        grid[i][j] = '0';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}

上一篇     下一篇