分享
UESTC 1218 Ancient Go (我的递归~~)
theArcticOcean · · 1881 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
http://acm.uestc.edu.cn/#/problem/show/1221
大意: 围棋判定,能不能下一步棋使得对手死去至少一个棋子。
对递归理解不深入导致开始不停RE(反复递归调用致使栈溢出),我去~~
还有一个致命的bug那就是整个o区域应该只有一口气,而不是单个一子的气数是1。
这种递归写出来是错误的,vis[q1][q2]应该是完成了check后才=1,而在进入后立刻=1会影响递归的结果。
AC 代码:
#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;
}
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1881 次点击
下一篇:Go语言圣经 2.3-复数
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
http://acm.uestc.edu.cn/#/problem/show/1221
大意: 围棋判定,能不能下一步棋使得对手死去至少一个棋子。
对递归理解不深入导致开始不停RE(反复递归调用致使栈溢出),我去~~
还有一个致命的bug那就是整个o区域应该只有一口气,而不是单个一子的气数是1。
这种递归写出来是错误的,vis[q1][q2]应该是完成了check后才=1,而在进入后立刻=1会影响递归的结果。
AC 代码:
#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;
}