四连通和八连通岛数不同

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

islands 已经写好，D4、D8 也已定义。补全 main：同一张网格跑两遍，把两个岛数拼起来输出（四连通在前）。

本节的网格（四行四列，1 是陆地，0 是海）：1100 / 1001 / 0010 / 1000。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 写一个洪泛填充拓扑序是什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

vector<vector<int>> GRID_MAP = {{1, 1, 0, 0}, {1, 0, 0, 1}, {0, 0, 1, 0}, {1, 0, 0, 0}};
const vector<pair<int, int>> D4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const vector<pair<int, int>> D8 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

pair<int, vector<int>> islands(const vector<vector<int>>& g, const vector<pair<int, int>>& dirs) {
    int m = g.size(), n = g[0].size();
    vector<vector<bool>> seen(m, vector<bool>(n, false));
    int cnt = 0;
    vector<int> sizes;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] != 1 || seen[i][j]) continue;
            cnt++;
            vector<pair<int, int>> st = {{i, j}};
            seen[i][j] = true;
            int sz = 0;
            while (!st.empty()) {
                auto [x, y] = st.back();
                st.pop_back();
                sz++;
                for (auto [dx, dy] : dirs) {
                    int a = x + dx, b = y + dy;
                    if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] == 1 && !seen[a][b]) {
                        seen[a][b] = true;
                        st.push_back({a, b});
                    }
                }
            }
            sizes.push_back(sz);
        }
    }
    return {cnt, sizes};
}

int main() {
    // TODO: 分别用 D4、D8 各数一次，用 / 拼起来输出
    cout << islands(GRID_MAP, D4).first << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

四连通和八连通岛数不同

更多题目

全部评论