題目

給定一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，計算島嶼的數(shù)量。一個島被水包圍，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設網(wǎng)格的四個邊均被水包圍。

示例 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;
    }
    /**
    * 遍歷跟此陸地有關(guān)聯(lián)的地，并把值改成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;
    }
};