leetcode200岛屿的数量

题目

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:
输入:
11110
11010
11000
00000
输出: 1

示例 2:
输入:
11000
11000
00100
00011
输出: 3

代码和分析

class Solution {
public:
    int n,m;
    int numIslands(vector<vector<char>>& grid) {
        n = grid.size();
        if(n==0)
            return 0;
        int num = 0;
        m=grid[0].size();
        //遍历，找到每一个1
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(grid[i][j] == '1'){
                    travel(grid,i,j);
                    num++;
                }
            }
        }
        return num;
    }
    /**
    * 遍历跟此陆地有关联的地，并把值改成0
    **/
    void travel(vector<vector<char>>& grid,int x,int y){
        if(grid[x][y] == '0')
            return;
        grid[x][y] = '0';
        //左边寻找
        if(x>0)
            travel(grid,x-1,y);
        //上边
        if(y>0)
            travel(grid,x,y-1);
        //右边
        if(x<n-1)
            travel(grid,x+1,y);
        //下边
        if(y<m-1)
            travel(grid,x,y+1);
        //grid[x][y] = 1;
    }
};