hdu2216 Game III (BFS)

it2022-05-06  16

我实在是无语了,为什么一定要用scanf("%s",map[i])或者 gets(map[i]),我用scanf("%c",map[i][j]) 就wa了n次还是错

改了之后,一次就A了

题目的意思比较好理解,就是Z占据了主导权,S一直跟着Z做反方向的运动,若S遇到墙,则原定不动。

这题目是一个比较基础的BFS吧,只需要用一个四维的数组标记俩个人的状态

#include<iostream> #include<algorithm> #include<queue> #include<math.h> using namespace std; bool vis[25][25][25][25]; int si,sj,ei,ej,n,m,ans; char g[25][25]; int dir1[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int dir2[4][2]={{0,-1},{0,1},{-1,0},{1,0}}; struct state { int x1,x2,y1,y2; int cnt; state(int a=0,int b=0,int c=0,int d=0,int e=0):x1(a),y1(b),x2(c),y2(d),cnt(e){} }; queue<state> Q; void BFS() { vis[si][sj][ei][ej]=true; Q.push(state(si,sj,ei,ej,0)); state tmp; while(!Q.empty()) { tmp=Q.front(); Q.pop(); if((abs(tmp.x1-tmp.x2)==1&&tmp.y1==tmp.y2)||(tmp.x1==tmp.x2 && abs(tmp.y1-tmp.y2)==1)||(tmp.x1==tmp.x2&&tmp.y1==tmp.y2)) { ans=tmp.cnt; return ; } for(int k=0;k<4;k++) { int i=tmp.x1+dir1[k][0]; int j=tmp.y1+dir1[k][1]; int l=tmp.x2+dir2[k][0]; int c=tmp.y2+dir2[k][1]; if(i>=n||i<0 || j>=m || j<0) continue; if(g[i][j]=='X') continue; if(l>=n||l<0 || c>=m || c<0) l=tmp.x2,c=tmp.y2; else if(g[l][c]=='X') l=tmp.x2,c=tmp.y2; if(!vis[i][j][l][c]) { vis[i][j][l][c]=true; Q.push(state(i,j,l,c,tmp.cnt+1)); } } } } int main() { while(scanf("%d %d",&n,&m)==2) { getchar(); for(int i=0;i<n;i++) { gets(g[i]); //getchar(); for(int j=0;j<m;j++) { // scanf("%c",&g[i][j]);就这里让我wa了n次 if(g[i][j]=='Z') si=i,sj=j,g[i][j]='.'; if(g[i][j]=='S') ei=i,ej=j,g[i][j]='.'; } } while(!Q.empty()) Q.pop(); memset(vis,false,sizeof(vis)); ans=-1; BFS(); if(ans==-1) puts("Bad Luck!"); else printf("%d\n",ans); } return 0; }

 

转载于:https://www.cnblogs.com/nanke/archive/2011/11/26/2264220.html

相关资源:数据结构—成绩单生成器

最新回复(0)