- 填海造岛(land)
题解
- @ 2026-4-26 14:48:20
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
const int MAXN = 1005;
int g[MAXN][MAXN];
int id[MAXN][MAXN]; // 每个陆地属于哪个块
int sz[MAXN * MAXN]; // 每个块的大小
int n, idx;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void dfs(int x, int y) {
id[x][y] = idx;
sz[idx]++;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
if (g[nx][ny] == 1 && id[nx][ny] == 0) {
dfs(nx, ny);
}
}
}
}
int main() {
freopen("land.in","r",stdin);
freopen("land.out","w",stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> g[i][j];
}
}
idx = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] == 1 && id[i][j] == 0) {
idx++;
dfs(i, j);
}
}
}
int ans = 0;
// 全是陆地的情况
if (idx == 1) {
cout << sz[1] << endl;
return 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] == 0) {
unordered_set<int> st;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
if (id[nx][ny] != 0) {
st.insert(id[nx][ny]);
}
}
}
int sum = 1;
for (int x : st) sum += sz[x];
if (sum > ans) ans = sum;
}
}
}
// 如果没有 0(全 1)
if (ans == 0) ans = n * n;
cout << ans << endl;
return 0;
}
0 comments
No comments so far...
Information
- ID
- 3165
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 19
- Accepted
- 4
- Uploaded By