UESTC 1218 Ancient Go (我的递归~~)

theArcticOcean · · 1047 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

大意: 围棋判定,能不能下一步棋使得对手死去至少一个棋子。
对递归理解不深入导致开始不停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;
}





有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:theArcticOcean

查看原文:UESTC 1218 Ancient Go (我的递归~~)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1047 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传