題目鏈接
tag:
- Medium；
- DFS；
question：
??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:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
思路：
??這道求島嶼數(shù)量的題的本質(zhì)是求矩陣中連續(xù)區(qū)域的個數(shù)挥下，很容易想到需要用深度優(yōu)先搜索 DFS 來解揍魂，我們需要建立一個 visited 數(shù)組用來記錄某個位置是否被訪問過，對于一個為 ‘1’ 且未被訪問過的位置棚瘟，我們遞歸進入其上下左右位置上為 ‘1’ 的數(shù)现斋，將其 visited 對應值賦為 true，繼續(xù)進入其所有相連的鄰位置偎蘸，這樣可以將這個連通區(qū)域所有的數(shù)找出來庄蹋，并將其對應的 visited 中的值賦 true，找完相鄰區(qū)域后迷雪，我們將結(jié)果 res 自增1限书，然后我們在繼續(xù)找下一個為 ‘1’ 且未被訪問過的位置，以此類推直至遍歷完整個原數(shù)組即可得到最終結(jié)果章咧，代碼如下：
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));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0' || visited[i][j]) continue;
helper(grid, visited, i, j);
++res;
}
}
return res;
}
void helper(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
visited[x][y] = true;
helper(grid, visited, x - 1, y);
helper(grid, visited, x + 1, y);
helper(grid, visited, x, y - 1);
helper(grid, visited, x, y + 1);
}
};
