UESTC 1218 Ancient Go （我的递归~~）

theArcticOcean · · 1426 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

http://acm.uestc.edu.cn/#/problem/show/1221

大意： $9 \times 9$ 围棋判定，能不能下一步棋使得对手死去至少一个棋子。

对递归理解不深入导致开始不停RE（反复递归调用致使栈溢出），我去~~

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char g[50][50];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool vis[50][50];
int qi;
void check(int q1,int q2){
    if(g[q1][q2]!='o'||vis[q1][q2]) return ;
    int ans=0;
    for(int i=0;i<4;i++){
        int x=q1+dir[i][0];
        int y=q2+dir[i][1];
        if(x<0||x>=9||y<0||y>=9||vis[x][y]) continue;
        if(g[x][y]=='x') continue;
        if(g[x][y]=='o'&&!vis[x][y]){
            check(x,y);   //就是这里，我注释了就错了，不注释就RE
            vis[x][y]=1;
        }
        if(g[x][y]=='.'){
            ans++;
        }
    }
    qi=max(qi,ans);
    vis[q1][q2]=1;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,t=1;
    char ch;
    cin>>n;
    while(n--){
        for(int i=0;i<9;i++){
           scanf("%s",g[i]);
        }
        bool flag=0;
        for(int i=0;i<9;i++){
            if(flag) break;
            for(int j=0;j<9;j++){
                if(g[i][j]=='o'){
                   qi=0;
                   memset(vis,0,sizeof(vis));
                   check(i,j);
                   if(qi==1){
                        flag=1;
                        break;
                   }
                }
            }
        }
        printf("Case #%d: ",t++);
        if(flag) puts("Can kill in one move!!!");
        else puts("Can not kill in one move!!!");
    }
    return 0;
}

还有一个致命的bug那就是整个o区域应该只有一口气，而不是单个一子的气数是1。

void check(int q1,int q2){
    if(vis[q1][q2]) return ;
    vis[q1][q2]=1;
    for(int i=0;i<4;i++){
        int x=q1+dir[i][0];
        int y=q2+dir[i][1];
        if(x<0||x>=9||y<0||y>=9||vis[x][y]) continue;
        if(g[x][y]=='x') continue;
        if(g[x][y]=='o'){
            check(x,y);
        }
        if(g[x][y]=='.'&&!use[x][y]){
            live++;
            use[x][y]=1;
        }
    }
}

这种递归写出来是错误的，vis[q1][q2]应该是完成了check后才=1，而在进入后立刻=1会影响递归的结果。
AC 代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char g[12][12];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool vis[12][12],use[12][12];
int live;
void check(int q1,int q2){
    if(vis[q1][q2]) return ;
    for(int i=0;i<4;i++){
        int x=q1+dir[i][0];
        int y=q2+dir[i][1];
        if(x<0||x>=9||y<0||y>=9||use[x][y]) continue;
        if(g[x][y]=='.'){
            live++;
            use[x][y]=1;
        }
    }
    vis[q1][q2]=1;
    for(int i=0;i<4;i++){
        int x=q1+dir[i][0];
        int y=q2+dir[i][1];
        if(x<0||x>=9||y<0||y>=9||vis[x][y]) continue;
        if(g[x][y]=='o') check(x,y);
    }
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,t=1;
    char ch;
    cin>>n;
    while(n--){
        for(int i=0;i<9;i++){
           scanf("%s",g[i]);
        }
        memset(vis,0,sizeof(vis));
        bool flag=0;
        for(int i=0;i<9;i++){
            if(flag) break;
            for(int j=0;j<9;j++){
                if(g[i][j]=='o'&&!vis[i][j]){
                   live=0;
                   memset(use,0,sizeof(use));
                   check(i,j);
                   if(live==1){
                        flag=1;
                        //printf("%d %d %d\n",i,j,temp);
                        break;
                   }
                }
            }
        }
        printf("Case #%d: ",t++);
        if(flag) puts("Can kill in one move!!!");
        else puts("Can not kill in one move!!!");
    }
    return 0;
}

有疑问加站长微信联系（非本文作者）