continental divider.cc

continental divider.cc

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define input(x) cin >> x
#define print(x) cout << x << endl

const int SIZE = 512;

const int mx[] = {0, 1, 0, -1};
const int my[] = {-1, 0, 1, 0};

int n, sea_cnt;
char g[SIZE][SIZE];
int nr[SIZE][SIZE];
int cnc[SIZE][SIZE];

void find_sea(int y, int x) {
    if (g[y][x] != '0') {
        return;
    }
    nr[y][x] = sea_cnt;
    for (int i = 0; i < 4; i++) {
        int ny = y + my[i];
        int nx = x + mx[i];
        if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
            find_sea(ny, nx);
        }
    }
}

int dfs(int y, int x) {
    if (cnc[y][x] != -1) {
        return cnc[y][x];
    }
    cnc[y][x] = 0;

    // if this node is a part of a sea
    if (nr[y][x] != -1) {
        cnc[y][x] |= (1 << nr[y][x]);
        return cnc[y][x];
    }

    for (int i = 0; i < 4; i++) {
        int ny = y + my[i];
        int nx = x + mx[i];
        if (ny >= 0 && ny < n && nx >= 0 && nx < n && g[y][x] > g[ny][nx]) {
            cnc[y][x] |= dfs(ny, nx);
        }
    }
    return cnc[y][x];
}

int main() {
    sea_cnt = 0;
    input(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int u;
            scanf("%d", &u);
            g[i][j] = u + '0';
        }
    }
    memset(nr, -1, sizeof(nr));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] != '0' || nr[i][j] != -1) {
                continue;
            }
            find_sea(i, j);
            sea_cnt++;
        }
    }

    memset(cnc, -1, sizeof(cnc));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (cnc[i][j] != -1) {
                continue;
            }
            dfs(i, j);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (cnc[i][j] == (1 << sea_cnt) -1) {
                printf("<%d, %d>\n", i, j);
            }
        }
    }
    return 0;
}