题解：UVA12987 Ancient Go

chenyizhen · 2025-04-29 20:43:16 · 题解

题意：x 能否把 o 围起来。

思路：

遍历白子连通块 ，如果只差一个就可以围起来，即符合题目要求。

附：在做本题的时候一开始的思路是并查集，在一个集合里就可以围圈，但是一看数据范围，直接爆搜！！！

还是补一道并查集套圈的题：信息学奥赛一本通 1347 - 格子游戏，有兴趣的可以做一下。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
inline void read(int &a){
    char ch;
    int f=1,k=0;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    a=k*f;
}
int T,n=9,vis[10][10],cnt;
char a[10][10];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int dfs(int x,int y){
    int tot=0;
    if(x<1||x>n||y<1||y>n) return 0;
    if(vis[x][y]) return 0;
    vis[x][y]=1;
    if(a[x][y]=='.') return 1;
    if(a[x][y]=='x') return 0;
    for(int i=0;i<4;i++){
        tot+=dfs(x+dx[i],y+dy[i]);
    }
    return tot;
}

signed main(){
    read(T);
    while(T--){
        int flg=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(a[i][j]=='o'&&!vis[i][j]){
                    if(dfs(i,j)==1) flg=1;
                    memset(vis,0,sizeof(vis));
                }
            }
        }
        cout<<"Case #"<<++cnt<<": ";
        if(flg) cout<<"Can kill in one move!!!\n";
        else cout<<"Can not kill in one move!!!\n";     
    }
    return 0;
}