1 条题解
-
0
100分代码:
#include <bits/stdc++.h> using namespace std; int n = 10, m = 10; // 固定为10x10,但可以根据需要调整 vector<vector<int>> a; // 用 vector 实现动态数组 vector<vector<int>> vis; // 访问标记数组 int cnt = 0; int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; struct node { int x, y; }; // 广度优先搜索,标记从边界开始的空白区域 void bfs(int x0, int y0) { a[x0][y0] = 1; vis[x0][y0] = 1; queue<node> q; q.push({x0, y0}); while (!q.empty()) { node curr = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = curr.x + dir[i][0]; int ny = curr.y + dir[i][1]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0 && vis[nx][ny] == 0) { vis[nx][ny] = 1; a[nx][ny] = 1; q.push({nx, ny}); } } } } // 计算内部分隔的区域 void bfs_cnt(int x0, int y0) { vis[x0][y0] = 1; cnt++; queue<node> q; q.push({x0, y0}); while (!q.empty()) { node curr = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = curr.x + dir[i][0]; int ny = curr.y + dir[i][1]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0 && vis[nx][ny] == 0) { vis[nx][ny] = 1; q.push({nx, ny}); cnt++; } } } } int main() { // 初始化动态数组 a.resize(n + 1, vector<int>(m + 1, 0)); vis.resize(n + 1, vector<int>(m + 1, 0)); // 输入数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } // 从上下边界进行BFS标记外部区域 for (int j = 1; j <= m; j++) { if (a[1][j] == 0) bfs(1, j); if (a[n][j] == 0) bfs(n, j); } // 从左右边界进行BFS标记外部区域 for (int i = 1; i <= n; i++) { if (a[i][1] == 0) bfs(i, 1); if (a[i][m] == 0) bfs(i, m); } // 对内部的0进行计数 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] == 0 && vis[i][j] == 0) { bfs_cnt(i, j); } } } cout << cnt << endl; return 0; }
- 1
信息
- ID
- 837
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 15
- 已通过
- 4
- 上传者