題目
給定一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，計算島嶼的數(shù)量辈赋。一個島被水包圍鲫忍，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設(shè)網(wǎng)格的四個邊均被水包圍钥屈。
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1
示例 2:
輸入:
11000
11000
00100
00011
輸出: 3
解題思路
使用DFS深度優(yōu)先算法
代碼
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.size() == 0) return 0;
vector<vector<char>> temp = grid;
int count = 0;
for(int i=0; i < temp.size(); i++){ //遍歷grid
for(int j=0; j < temp[0].size(); j++){
if(temp[i][j] == '1'){ //如果發(fā)現(xiàn)是‘1’悟民，那么找到邊緣，這樣就訪問了一個land
visitland(temp, i, j); //訪問一個land
count++;
}
}
}
return count;
}
void visitland(vector<vector<char>>& grid, int i, int j){
if(i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size()){
if(grid[i][j] == '1'){
grid[i][j] = '0'; //把訪問過的變?yōu)?0'篷就，表示已經(jīng)訪問過了
visitland(grid, i+1, j);
visitland(grid, i-1, j);
visitland(grid, i, j+1);
visitland(grid, i, j-1);
}
}
}
};
