Karl's Nest
0%

leetcode-day-17

Posted on In
Day-17 Number of Islands

LeetCode 30 days Challenge - Day 17

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

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:

1
2
3
4
5
6
7
Input:
11110
11010
11000
00000

Output: 1

Example 2:

1
2
3
4
5
6
7
Input:
11000
11000
00100
00011

Output: 3

Solution

题目要求分析：给定一个只含有字符0和1的二维数组，其中0代表海洋、1代表陆地，连接在一起的陆地构成一座岛屿，求地图中岛屿的个数。

解法：

典型的DFS或BFS问题，本题中可以直接修改grid值，在访问过陆地(1)之后可以将之修改为海洋(0)，无需额外设立一个访问数组。

具体过程如下：

  1. 新建一个变量nums记录岛屿数。
  2. 遍历整个数组，遇到为陆地的元素时，以该元素位置为起点进行深度优先搜索，确保其所在岛屿所有的陆地都被访问到并且修改为海洋。

因为每次访问都保证其所在岛屿所有的陆地都被访问到并且修改为海洋，所以遇到新的陆地时将nums加1。

注：本题所给的grid数组是char 字符型数组！进行判断时候不可以写if (grid[i][j])而要写if (grid[i][j]=='1')。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void dfs(int x, int y, vector<vector<char>>& grid) {
    if (x<0 || x>grid.size()-1 || y<0 || y>grid[0].size()-1) return;
    if (grid[x][y]=='1') {
        grid[x][y] = 0;
        for (auto dir : dirs) dfs(x+dir[0], y+dir[1], grid);
    }
}

int numIslands(vector<vector<char>>& grid) {
    int nums = 0;
    for (int i = 0; i<grid.size(); i++) {
        for (int j = 0; j<grid[0].size(); j++) {
            if (grid[i][j]=='1') {
                nums++;
                dfs(i, j, grid);
            }
        }
    }
    return nums;
}

传送门：Number of Islands

Karl