LeetCode：连通域

发表于 | 分类于

这里主要是对一些与连通域计算相关的题目做一个汇总。这类题的出题形式比较单一，一般都是，求矩阵中连续区域的个数，连续区域的面积，连续区域的周长，最大连续区域的面积等等。

连通域个数

例题、LeetCode 200 Number of Islands

给定一个二维矩阵地图，‘1’表示陆地，‘0’表示水域。计算陆地（小岛）的个数。岛被水包围，并通过水平或垂直连接相邻的陆地而形成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

从题目的意思和给出的例子可以看出，我们只需要计算上下左右四个方向就行，即四连通域。很容易想到使用深度优先搜索DFS来求解，我们需要建立一个visited数组用来记录某个位置是否被访问过。对于一个为‘1’且未被访问过的位置，我们递归进入其上下左右位置上为‘1’的数，将其visited对应值赋为true，继续进入其所有相连的邻位置，这样可以将这个连通区域所有的数找出来，并将其对应的visited中的值赋true，找完此区域后，我们将结果res自增1，然后我们在继续找下一个为‘1’且未被访问过的位置，以此类推直至遍历完整个原数组即可得到最终结果。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
        vector<vector<int>> dirs{ { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };//左右，上下四个方向
	    for (auto dir : dirs)
		    numIslandsDFS(grid, visited, x + dir[0], y + dir[1]);
    }
};

连通域最大面积

例题、LeetCode 695 Max Area of Island

这道题和上面那道题差不多，只不过这道题是需要计算出每个岛屿的大小，即连通域的面积。可以先用递归来做，遇到为1的点，调用递归函数，在递归函数中，我们首先判断i和j是否越界，还有grid[i][j]是否为1，我们没有用visited数组，而是直接修改了grid数组，遍历过的标记为-1。如果合法，那么cnt自增1，并且更新结果res，然后对其周围四个相邻位置分别调用递归函数即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void helper(vector<vector<int>>& grid, int x, int y, int &cnt, int&res)
{
	if (x < 0 || x >= grid.size()) return;
	if (y < 0 || y >= grid[0].size()) return;
	if (grid[x][y] != 1) return;
	grid[x][y] *= -1;
	cnt++;
	res = max(res, cnt);
	vector<vector<int>> dirs{ { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
	for (auto dir : dirs)
		helper(grid, x + dir[0], y + dir[1], cnt, res);
}
int maxAreaOfIsland(vector<vector<int>>& grid) 
{
	if (grid.empty() || grid[0].empty()) return 0;
	int m = grid.size(), n = grid[0].size(), res = 0;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
	 		if (grid[i][j] != 1)continue;
			int cnt = 0;
			helper(grid, i, j, cnt, res);
		}
	}
	return res;
}

连通域周长

例题、LeetCode 463 Island Perimeter

给定给了我们一个格子图，若干连在一起的格子形成了一个小岛，规定了图中有且只有一个相连的岛，且岛中没有湖，让我们求岛的周长。

1
2
3
4
5
6
7
8
9
Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

这道题在LeetCode上是难度为easy的题目。每个格子有四条边，这道题一开始想着对每个为‘1’的位置自加4，然后分别判断这个位置的上下左右四个位置是否为‘1’，然后相应的减2，后来看到网上的解法，其实没有必要复杂，因为我们是从左上角遍历到右下角，因此只需要判断当前位置的上面或左边位置是否为‘1’，是的话就减2。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int islandPerimeter(vector<vector<int>>& grid)
{
	if (grid.empty() || grid[0].empty()) return 0;
	int m = grid.size(), n = grid[0].size(), res = 0;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			if (grid[i][j] != 1)continue;
			res += 4;
			if (j>0&&grid[i][j - 1] == 1)res -= 2;
			if (i>0&&grid[i - 1][j] == 1)res -= 2;
		}
	}
	return res;
}

综合

例题、群体个数以及最大群体人数

这里不得不提及上次参加2019年校招今日头条的图像算法笔试题，其中就有一道和这一模一样的题。下面是原题的截图。

这道题和上面那道题同出一辙，只不过改了应用背景，以及四连通域换成八连通域，还附加了一个计算最大连通域的面积的计算。求解这道题只需要在上面那道题的基础上稍作修改即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static const auto speedup = [](){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	return nullptr;
}();
 void numIslandsDFSAndCnt(vector<vector<char> > &grid, vector<vector<bool> > &visited,
	 int x, int y, int&cnt) 
 {
	 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;
	 cnt++;
	vector<vector<int>> dirs{ { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 },
	{ -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 } };//左右上下，斜对角共八个方向
	 for (auto dir:dirs)
		 numIslandsDFSAndCnt(grid, visited, x + dir[0], y + dir[1], cnt);
	
 }
vector<int>numIslandsAndMaxCnt(vector<vector<char> > &grid) {
	 if (grid.empty() || grid[0].empty()) return { 0, 0 };
	 int m = grid.size(), n = grid[0].size(), res = 0;
	 vector<vector<bool> > visited(m, vector<bool>(n, false));
	 int maxValue = 0;
	 for (int i = 0; i < m; ++i) {
		 for (int j = 0; j < n; ++j) {
			 if (grid[i][j] == '1' && !visited[i][j]) {
				 int cnt = 0;
				 numIslandsDFSAndCnt(grid, visited, i, j, cnt);
				 maxValue = max(maxValue, cnt);
				 ++res;
			 }
		 }
	 }
	
	 return{ res, maxValue };
 }

由此可见，刷题的必要性，很多公司的笔试题基本上都是在LeetCode或者牛客网都能找到原型。