leetcode_day55

本文最后更新于 2024年7月16日 中午

今日内容：

孤岛的总面积

题目：

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

思路：

先绕地图边缘遍历，遇到陆地就搜索，把整块地都变成水，然后再遍历地图，得到的就全是孤岛，计算总面积。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
 
using namespace std;
 
const int N = 55;//题目限制最大50，开个55
 
int n, m;//长宽
int cnt;//计数器
int g[N][N];//地图
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//方向
 
void dfs(int sx, int sy)
{
    g[sx][sy] = 0;//直接变水
 
    for (int i = 0; i < 4; i++)//四个方向
    {
        int a = sx + dx[i], b = sy + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] == 0) continue;
        g[a][b] = 0;//变水
        cnt++;//计数孤岛
        dfs(a, b);
    }
}
 
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
 
    for (int i = 0; i < n; i++)
    {
        if (g[i][0] == 1) dfs(i, 0);  //左边
        if (g[i][m - 1] == 1) dfs(i, m - 1);  // 右边
    }
    for (int i = 0; i < m; i++)
    {
        if (g[0][i] == 1) dfs(0, i); // 上边
        if (g[n - 1][i] == 1) dfs(n - 1, i); // 下边
    }
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (g[i][j] == 1)
            {
                cnt = 1;//记录当前
                dfs(i, j);
                res += cnt;
            }
        }
    }
    cout << res << endl;
    return 0;
}

沉默孤岛

题目：

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出将孤岛“沉没”之后的岛屿矩阵。 注意：每个元素后面都有一个空格

思路：

溜边遍历，把靠边的陆地全变成2，再遍历一次，把不是2的都变水，就能够沉掉孤岛。

代码

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
38
39
40
41
42
43
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a;i < b;i++)
using namespace std;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0 ,-1};//方向
void dfs(vector<vector<int>>& grid, int x, int y) {
    grid[x][y] *= 2;//0就0，1就2
    if(!grid[x][y]) return ;//已经遇到水了，不用继续走了
    rep(k, 0, 4) {
        int i = x + dir[k][0];
        int j = y + dir[k][1];
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) continue;
        if(grid[i][j] == 1) {
            grid[i][j] = 2;
            dfs(grid, i, j);
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> grid(N, vector<int>(M, 0));
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < M;j++) {
            cin >> grid[i][j];
        }
    }
    rep(i, 0, N) {//溜左右
        dfs(grid, i, 0);
        dfs(grid, i, M-1);
    }
    rep(i, 0, M) {//溜上下
        dfs(grid, 0, i);
        dfs(grid, N-1, i);
    }
    rep(i, 0, N) {//溜全图
        rep(j, 0, M) {
            cout << (int)(grid[i][j] > 1) << ' ';//是2才输出
        }
        cout << endl;
    }
    return 0;
}

水流问题

题目：

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入描述

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

输出描述

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

思路：

不能暴力，要优化，仍然溜边，分别记录一组边界和二组边界上每个边点能够去到的地方，即一组边界和二组边界都有着一张图，上面true的地方能作上游，false的地方不能。

最后再遍历全图，如果一组边界和二组边界都能将其作为上游，那么就是目标点，输出。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};//方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    if (visited[x][y]) return;//走过，不用再走

    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
        if (grid[x][y] > grid[nextx][nexty]) continue; // 注意：这里是从低向高遍历，逆流而上

        dfs (grid, visited, nextx, nexty);
    }
    return;
}



int main() {

    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    // 标记从第一组边界上的节点出发，可以遍历的节点
    vector<vector<bool>> firstBorder(n, vector<bool>(m, false));

    // 标记从第一组边界上的节点出发，可以遍历的节点
    vector<vector<bool>> secondBorder(n, vector<bool>(m, false));

    // 从最上和最下行的节点出发，向高处遍历
    for (int i = 0; i < n; i++) {
        dfs (grid, firstBorder, i, 0); // 遍历最左列，接触第一组边界
        dfs (grid, secondBorder, i, m - 1); // 遍历最右列，接触第二组边界
    }

    // 从最左和最右列的节点出发，向高处遍历
    for (int j = 0; j < m; j++) {
        dfs (grid, firstBorder, 0, j); // 遍历最上行，接触第一组边界
        dfs (grid, secondBorder, n - 1, j); // 遍历最下行，接触第二组边界
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果
            if (firstBorder[i][j] && secondBorder[i][j]) cout << i << " " << j << endl;;
        }
    }
}

建造最大岛屿

题目：

给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示最大的岛屿面积。如果矩阵中不存在岛屿，则输出 0。

思路：

不能暴力，先遍历全图，用不同的mark标记不同的岛屿，开个map记录标号mark-面积count的序对[mark, count]，最后再遍历全图，对每个水地块计算其周围四格邻接的不同岛屿的面积总和，取最大值。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a;i < b;i++)
using namespace std;

int N,M;
int cnt;//单个岛屿计数器

int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};//方向
void dfs(vector<vector<int>> & grid, int x, int y, int mark) {
    grid[x][y] = mark;//用mark覆盖，相当于着色
    cnt++;
    rep(m, 0, 4) {
        int i = x + dir[m][0];
        int j = y + dir[m][1];
        if(i < 0 || i >= N || j < 0 || j >= M || grid[i][j] != 1) continue;
        dfs(grid, i, j, mark);
    }
}

int main() {
    cin >> N >> M;
    vector<vector<int>> grid(N, vector<int>(M, 0));
    rep(i, 0, N) {
        rep(j ,0, M) {
            cin >> grid[i][j];
        }
    }
    //先遍历地图记录岛屿-面积
    unordered_map<int, int> map;
    int mark = 2;
    rep(i, 0, N) {
        rep(j, 0, M) {
            if(grid[i][j] == 1) {
                cnt = 0;
                dfs(grid, i, j, mark);
                map[mark] = cnt;
                mark++;
            }
        }
    }
    //遍历海洋，计算相邻岛屿面积之和，取最大值
    int ans = 0, temp = 0;
    rep(i, 0, N) {
        rep(j, 0, M) {
            if(grid[i][j] > 0) continue;
            //将相邻的不同岛屿面积相加,unordered_set去重岛屿
            unordered_set<int> set;
            temp = 1;
            rep(m, 0, 4) {
                int x = i + dir[m][0];
                int y = j + dir[m][1];
                if(x < 0 || x >= N || y < 0 || y >= M || grid[x][y] == 0) continue;
                if(set.find(grid[x][y]) != set.end()) continue;
                else {
                    temp += map[grid[x][y]];
                    set.insert(grid[x][y]);
                }
            }
            ans = ans > temp ? ans : temp;
        }
    }
    if(ans == 0) cout<< N * M;//没水全是地，直接返回地图大小
    else cout << ans;
    return 0;
}
#leetcode
leetcode_day55
https://novelyear.github.io/2024/07/16/leetcode-day55/
作者
Leoo Yann
更新于
2024年7月16日
许可协议