当前位置：首页 > news >正文

代码随想录-- 第一天图论 --- 岛屿的数量

news 2025/2/21 2:31:07

99 统计岛屿的数量 c++

99. 岛屿数量

#include <iostream>
#include <vector>
#include <queue>using namespace std;struct MGraph {int numVertices, numEdges;vector<vector<int>> Edge;
};int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};void dfs(MGraph& mGraph, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; ++i) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx >= 0 && nextx < mGraph.Edge.size() && nexty >= 0 && nexty < mGraph.Edge[0].size() && !visited[nextx][nexty] && mGraph.Edge[nextx][nexty] == 1) {visited[nextx][nexty] = true;dfs(mGraph, visited, nextx, nexty);}}
}void bfs(MGraph& mGraph, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> q;visited[x][y] = true;q.push({x, y});while (!q.empty()) {auto [curx, cury] = q.front();q.pop();for (int i = 0; i < 4; ++i) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx >= 0 && nextx < mGraph.Edge.size() && nexty >= 0 && nexty < mGraph.Edge[0].size() && !visited[nextx][nexty] && mGraph.Edge[nextx][nexty] == 1) {visited[nextx][nexty] = true;q.push({nextx, nexty});}}}
}int main() {int M, N;cin >> M >> N;MGraph mGraph;mGraph.Edge.resize(M, vector<int>(N));for (int i = 0; i < M; ++i) {for (int j = 0; j < N; ++j) {cin >> mGraph.Edge[i][j];}}vector<vector<bool>> visited(M, vector<bool>(N, false));int result = 0;for (int i = 0; i < M; ++i) {for (int j = 0; j < N; ++j) {if (!visited[i][j] && mGraph.Edge[i][j] == 1) {result++;dfs(mGraph, visited, i, j); // 可以替换为 bfs 如果需要广度优先搜索}}}cout << result << endl;return 0;
}