54pts求助
  • 板块P4997 不围棋
  • 楼主koukou
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/30 13:10
  • 上次更新2025/7/30 17:17:45
查看原帖
54pts求助
1025097
koukou楼主2025/7/30 13:10
#include<bits/stdc++.h>
using namespace std;
const int N = 6e2 + 1;
bool vis[N * N];
char op, a[N][N];
int n, xx, yy, X, O, fa[N * N], q[N * N];
int W(int x, int y)
{
    if(x < 1 || y < 1 || x > n || y > n) return 0;
    return (x - 1) * n + y;
}
int find(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
bool check()
{
    char ch = 'X';
    if(op == 'X') ch = 'O';
    for(int k = (ch == 'X' ? X : O); k <= n * n; k++)
    {
        int i = (k - 1) / n + 1, j = (k - 1) % n + 1;
        if(a[i][j] == '.')
        {
            if(a[i - 1][j] == ch) q[find(W(i - 1, j))]--;
            if(a[i + 1][j] == ch) q[find(W(i + 1, j))]--;
            if(a[i][j - 1] == ch) q[find(W(i, j - 1))]--;
            if(a[i][j + 1] == ch) q[find(W(i, j + 1))]--;
            int Q = 4;
            if(a[i - 1][j] == op)
            {
                Q -= 2;
                if(!vis[find(W(i - 1, j))])
                {
                    vis[find(W(i - 1, j))] = 1;
                    Q += q[find(W(i - 1, j))];
                }
            }
            if(a[i + 1][j] == op)
            {
                Q -= 2;
                if(!vis[find(W(i + 1, j))])
                {
                    vis[find(W(i + 1, j))] = 1;
                    Q += q[find(W(i + 1, j))];
                }
            }
            if(a[i][j - 1] == op)
            {
                Q -= 2;
                if(!vis[find(W(i, j - 1))])
                {
                    vis[find(W(i, j - 1))] = 1;
                    Q += q[find(W(i, j - 1))];
                }
            }
            if(a[i][j + 1] == op)
            {
                Q -= 2;
                if(!vis[find(W(i, j + 1))])
                {
                    vis[find(W(i, j + 1))] = 1;
                    Q += q[find(W(i, j + 1))];
                }
            }
            vis[find(W(i - 1, j))] = vis[find(W(i + 1, j))] = vis[find(W(i, j - 1))] = vis[find(W(i, j + 1))] = 0;
            if(a[i - 1][j] == ch || i == 1) Q--;
            if(a[i + 1][j] == ch || i == n) Q--;
            if(a[i][j - 1] == ch || j == 1) Q--;
            if(a[i][j + 1] == ch || j == n) Q--;
            bool flag = (Q && q[find(W(i - 1, j))] && q[find(W(i + 1, j))] && q[find(W(i, j - 1))] && q[find(W(i, j + 1))]);
            if(a[i - 1][j] == ch) q[find(W(i - 1, j))]++;
            if(a[i + 1][j] == ch) q[find(W(i + 1, j))]++;
            if(a[i][j - 1] == ch) q[find(W(i, j - 1))]++;
            if(a[i][j + 1] == ch) q[find(W(i, j + 1))]++;
            if(flag)
            {
                q[W(i, j)] = Q;
                xx = i, yy = j;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    cin >> n;
    memset(q, 0x3f3f3f, sizeof(q));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            q[W(i, j)] = 0;
            fa[W(i, j)] = W(i, j);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(a[i - 1][j] == a[i][j] && a[i][j] != '.') fa[find(W(i, j))] = find(W(i - 1, j));
            if(a[i][j - 1] == a[i][j] && a[i][j] != '.') fa[find(W(i, j))] = find(W(i, j - 1));
            if(a[i - 1][j] == '.') q[find(W(i, j))]++;
            if(a[i + 1][j] == '.') q[find(W(i, j))]++;
            if(a[i][j + 1] == '.') q[find(W(i, j))]++;
            if(a[i][j - 1] == '.') q[find(W(i, j))]++;
        }
    }
    op = 'X';
    X = O = 1;
    while(check())
    {
        a[xx][yy] = op;
        if(a[xx - 1][yy] == op) fa[find(W(xx - 1, yy))] = find(W(xx, yy));
        if(a[xx + 1][yy] == op) fa[find(W(xx + 1, yy))] = find(W(xx, yy));
        if(a[xx][yy - 1] == op) fa[find(W(xx, yy - 1))] = find(W(xx, yy));
        if(a[xx][yy + 1] == op) fa[find(W(xx, yy + 1))] = find(W(xx, yy));
        char ch = 'X';
        if(op == 'X') ch = 'O';
        if(a[xx - 1][yy] == ch) q[find(W(xx - 1, yy))]--;
        if(a[xx + 1][yy] == ch) q[find(W(xx + 1, yy))]--;
        if(a[xx][yy - 1] == ch) q[find(W(xx, yy - 1))]--;
        if(a[xx][yy + 1] == ch) q[find(W(xx, yy + 1))]--;
        cout << xx << " " << yy << "\n";
        if(op == 'X') X = W(xx, yy) + 1;
        else O = W(xx, yy) + 1;
        op = (op == 'X' ? 'O' : 'X');
    }
    cout << "-1 -1";
    return 0; 
}
2025/7/30 13:10
加载中...