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

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

​​#include #include #include 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 #include #include #include 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。