并查集求调
  • 板块P4997 不围棋
  • 楼主YoungL
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/29 14:30
  • 上次更新2024/1/29 15:54:48
查看原帖
并查集求调
1050683
YoungL楼主2024/1/29 14:30
#include <bits/stdc++.h>
#define to_1d(x, y) ((x)*n+(y))
#define to_2d_x(x) ((x)/n)
#define to_2d_y(x) ((x)%n)
#define in_range(x, y) ((x) < n && (x) >= 0 && (y) < n && (y) >= 0)

using namespace std;
const int maxn = 600 + 5;
int set_[maxn*maxn], board[maxn][maxn], air[maxn*maxn], n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0,  1, -1};
queue<int> poses;
map<pair<int, int>, bool> vis;

int finds(int x) {
    if (set_[x] == x) return x;
    return set_[x] = finds(set_[x]);
}

void merge(int x, int y) {
    x = finds(x), y = finds(y);
    set_[x] = set_[y];
    if (x != y)
        air[y] += air[x];
}

bool can_put(int i, int j, int cur) {
    if (board[i][j]) return false;
    bool flag = true;
    int pos = to_1d(i, j), new_siz=0;
    for (int dir=0; dir<4; dir++) {
        int tx=i+dx[dir], ty=j+dy[dir];
        if (!in_range(tx, ty)) continue;
        if (!board[tx][ty]) new_siz++;
    }
    if (!new_siz) return false;
    for (int dir=0; dir<4; dir++) {
        int tx=i+dx[dir], ty=j+dy[dir], p = finds(to_1d(tx, ty));
        if (!in_range(tx, ty)) continue;
        if (!board[tx][ty]) continue;
        int tmp = air[p]-1;
        if (board[tx][ty] == cur) tmp += new_siz;
        if (tmp <= 0) flag = false;
    }
    if (!flag) {
        return false;
    } else {
        air[pos] = new_siz;
        board[i][j] = cur;
        for (int dir=0; dir<4; dir++) {
            int tx=i+dx[dir], ty=j+dy[dir], p = finds(to_1d(tx, ty));
            if (!in_range(tx, ty)) continue;
            if (!board[tx][ty]) continue;
            if (board[tx][ty] == cur)
                merge(pos, p);
            air[p]--;
        }
        return true;
    }
}

signed main() {
    scanf("%d", &n);
    for (int i=0; i<to_1d(n, n); i++) set_[i] = i;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            char c;
            scanf("%c", &c);
            if (c != '.' && c != 'X' && c != 'O') {
                j--;
                continue;
            }
            if (c == '.') board[i][j] = 0;
            if (c == 'X') board[i][j] = 1;
            if (c == 'O') board[i][j] = 2;
        }
    }
    // 计算气
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int airs = 0;
            if (!board[i][j])  {
                poses.push(to_1d(i, j));
                continue;
            }
            for (int dir=0; dir<4; dir++) {
                int tx = i+dx[dir], ty = j+dy[dir];
                if (!in_range(tx, ty)) continue;
                if (board[tx][ty] == board[i][j]) merge(to_1d(i, j), to_1d(tx, ty));
                if (!board[tx][ty]) airs++;
            }
            air[finds(to_1d(i, j))] += airs;

        }
    }
    int cur = 0; // 0: black, 1: white
    while (!poses.empty()) {
        int i, j;
        i = to_2d_x(poses.front()), j = to_2d_y(poses.front());
        poses.pop();
        if (can_put(i, j, cur+1))
            printf("%d %d\n", i+1, j+1),
            cur++,cur%=2;
        else if (vis[make_pair(to_1d(i, j), cur)]) break;
        else poses.push(to_1d(i, j)),
             vis[make_pair(to_1d(i, j), cur)] = true;
    }
    printf("-1 -1\n");
    return 0;
}
2024/1/29 14:30
加载中...