博文中会简要介绍Leetcode P0200题目分析及解题思路。
“Number of Islands”是一道比较基础的题目，这道题考察的就是搜索，既可以使用深度优先搜索，也可以使用广度优先搜索。
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: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
本题我使用了DFS来解决。维护一个二维布尔数组来记录访问过的“岛屿”位置，对于任意一个未访问的“岛屿”，以它为起点进行DFS，在二维布尔数组里标记这次搜索中访问过的所有岛屿，然后再寻找下一个未访问的“岛屿”作为起点。
以下是Java的题解代码实现。
class Solution {
public int numIslands(char[][] grid) {
if (grid.length == 0)
return 0;
int H = grid.length, W = grid[0].length, count = 0;
boolean[][] isVisited = new boolean[H][W];
for (int r=0; r<H; ++r) {
for (int c=0; c<W; ++c) {
if (grid[r][c] == '1' && !isVisited[r][c]) {
this.dfs(isVisited, grid, r, c, H, W);
++count;
}
}
}
return count;
}
private int[] dr = new int[] {1, -1, 0, 0};
private int[] dc = new int[] {0, 0, 1, -1};
private void dfs(boolean[][] isVisited, char[][] grid,
int row, int col, int H, int W) {
isVisited[row][col] = true;
for (int di=0; di<4; ++di) {
int r = row+dr[di];
int c = col+dc[di];
if (r >= 0 && r < H
&& c >= 0 && c < W
&& grid[r][c] == '1'
&& !isVisited[r][c]) {
this.dfs(isVisited, grid, r, c, H, W);
}
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size() == 0)
return 0;
int H = grid.size(), W = grid[0].size(), count = 0;
vector<vector<bool>> visited(H, vector<bool>(W, false));
for (int r=0; r<H; ++r) {
for (int c=0; c<W; ++c) {
if (grid[r][c] == '1' && !visited[r][c]) {
this->_Dfs(grid, visited, H, W, r, c);
++count;
}
}
}
return count;
}
private:
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
void _Dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited,
const int H, const int W, const int row, const int col) {
visited[row][col] = true;
for (int di=0; di<4; ++di) {
int r = row+dr[di];
int c = col+dc[di];
if (r >= 0 && r < H && c >= 0 && c < W
&& grid[r][c] == '1'
&& !visited[r][c]) {
this->_Dfs(grid, visited, H, W, r, c);
}
}
}
};