題目
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
解題之法
class Solution {
public:
int numIslands(vector<vector<char> > &grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<bool> > visited(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1' && !visited[i][j]) {
numIslandsDFS(grid, visited, i, j);
++res;
}
}
}
return res;
}
void numIslandsDFS(vector<vector<char> > &grid, vector<vector<bool> > &visited, int x, int y) {
if (x < 0 || x >= grid.size()) return;
if (y < 0 || y >= grid[0].size()) return;
if (grid[x][y] != '1' || visited[x][y]) return;
visited[x][y] = true;
numIslandsDFS(grid, visited, x - 1, y);
numIslandsDFS(grid, visited, x + 1, y);
numIslandsDFS(grid, visited, x, y - 1);
numIslandsDFS(grid, visited, x, y + 1);
}
};
分析
這道求島嶼數量的題的本質是求矩陣中連續(xù)區(qū)域的個數次洼，很容易想到需要用深度優(yōu)先搜索DFS來解蝶溶。
我們需要建立一個visited數組用來記錄某個位置是否被訪問過脓规，對于一個為‘1’且未被訪問過的位置运准，我們遞歸進入其上下左右位置上為‘1’的數菱属，將其visited對應值賦為true，繼續(xù)進入其所有相連的鄰位置损痰，這樣可以將這個連通區(qū)域所有的數找出來土至，并將其對應的visited中的值賦true，找完次區(qū)域后啡浊，我們將結果res自增1戳粒，然后我們在繼續(xù)找下一個為‘1’且未被訪問過的位置路狮，以此類推直至遍歷完整個原數組即可得到最終結果。
