#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