hdu 2216 Game III(BFS)

发布时间:2014-10-23 23:27:45
来源:分享查询网

这道题错了很多遍,主要错在两个地方。 一、不能用scanf("%c",&c)读入,这个是题目的原因,之前遇到过几次这个问题,很烦! 二、我特么的没有对vis初始化! 题目思路倒是很简单,一个人的状态不好记录,两个人放一块儿就很容易记录了。 #include<stdio.h> #include<string.h> #define N 25 int mark[N][N],vis[N][N][N][N]; int m,n; int dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}}; char s[N][N]; struct node { int x1,y1; int x2,y2; int cnt; }q[500000],a; int abs(int x) { if(x<0) return -x; return x; } int fun(node a) { int temp=abs(a.x1-a.x2)+abs(a.y1-a.y2); if(temp==1||temp==0) return 1; return 0; } int judge(int x,int y) { if(x<1||x>m||y<1||y>n) return 0; if(mark[x][y]==-1) return 0; return 1; } int BFS() { node cur,next; cur=a; vis[a.x1][a.y1][a.x2][a.y2]=1; if(fun(a)) return 0; int head,tail; head=tail=0; q[tail++]=cur; while(head!=tail) { cur=q[head++]; next.cnt=cur.cnt+1; for(int i=0;i<4;i++) { next.x1=cur.x1+dir[i][0]; next.y1=cur.y1+dir[i][1]; if(judge(next.x1,next.y1)) { next.x2=cur.x2+dir[3-i][0]; next.y2=cur.y2+dir[3-i][1]; if(!judge(next.x2,next.y2)) { next.x2=cur.x2; next.y2=cur.y2; } if(vis[next.x1][next.y1][next.x2][next.y2]==1) continue; if(fun(next)) return next.cnt; q[tail++]=next; vis[next.x1][next.y1][next.x2][next.y2]=1; } } } return -1; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { getchar(); for(int i=1;i<=m;i++) gets(s[i]+1); a.cnt=0; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { char c; c=s[i][j]; if(c=='.') mark[i][j]=0; else if(c=='X') mark[i][j]=-1; else if(c=='Z') { mark[i][j]=0; a.x1=i;a.y1=j; } else if(c=='S') { mark[i][j]=0; a.x2=i;a.y2=j; } } } int ans; memset(vis,0,sizeof(vis)); ans=BFS(); if(ans==-1) printf("Bad Luck!\n"); else printf("%d\n",ans); } return 0; }

返回顶部
查看电脑版