这个题真的非常郁闷,错了一下午、、、、、
明明思路非常的正确,怎么修改就是WA、、、
题意:
由起点到终点的最小时间。需要注意的是如果遇见@则此次只能fly并且@的下一步也只能fly。
分析:
看到题就明白是个有特殊条件的BFS。写好后一直WA,才知道每个状态需要记录power,三维数组记录状态。写好后就开始了悲剧的找错时光、、、、
漫长的一下午过去了,晚上也好一会了,还是没有发现究竟错在哪、、、、找了个跟自己的思路一样的AC的代码。一点点对照,仍旧没有找到原因,持续郁闷中
到底哪错啦??????????
我的代码:
#include<stdio.h> #include<queue> #include<iostream> #include<string.h> using namespace std; char N[81][81]; bool mark[81][81][81]; int A,B,T; int matrix[4][2]={0,1,0,-1,1,0,-1,0}; struct info { int a; int b; int step; int p;//剩余能量 }; info e; std::queue<info> Q; bool operator<(info x,info y) { return x.step>y.step; } int BFS(info x) { info y; Q.push(x); while(!Q.empty()) { x=Q.front();Q.pop(); if(x.step>T) return -1; if(N[x.a][x.b]=='L') return x.step; for(int i=0;i<4;i++) { y.a=x.a+matrix[i][0];y.b=x.b+matrix[i][1]; if(y.a>=0&&y.a<A&&y.b>=0&&y.b<B&&N[y.a][y.b]!='#') { //飞行 if(mark[y.a][y.b][x.p-1]==0&&x.p>0) { y.p=x.p-1; y.step=x.step+1; mark[y.a][y.b][y.p]=1; Q.push(y); } //walk if(mark[y.a][y.b][x.p]==0&&N[y.a][y.b]!='@'&&N[x.a][x.b]!='@') { y.p=x.p;y.step=x.step+2; mark[y.a][y.b][y.p]=1; Q.push(y); } } } } return -1; } int main() { int cnt=0;int P; while(~scanf("%d%d%d%d",&A,&B,&T,&P)) { memset(mark,0,sizeof(mark)); memset(N,0,sizeof(N)); getchar(); printf("Case %d:\n",++cnt); int i,j,k; info X; for(i=0;i<A;i++) { for(j=0;j<B;j++) { scanf("%c",&N[i][j]); if(N[i][j]=='Y') {X.a=i;X.b=j;X.step=0;X.p=P;mark[i][j][P]=1;} } getchar(); } int s=BFS(X); if(s<0) printf("Poor Yifenfei, he has to wait another ten thousand years.\n"); else printf("Yes, Yifenfei will kill Lemon at %d sec.\n",s); } return 0; }
AC的代码:【代码来自http://blog.csdn.net/swm8023/article/details/6765219】
#include <cstdio> #include <string.h> #include <queue> using namespace std; struct pos{ int r,c,p,s; pos(int w,int x,int y,int z){r=w,c=x,p=y,s=z;} }; int n,m,p,t,sr,sc,er,ec; bool vis[82][82][82]; int dr[]={0,0,1,-1},dc[]={1,-1,0,0}; char maze[82][82]; int bfs(){ queue<pos> q; memset(vis,0,sizeof vis); q.push(pos(sr,sc,p,0)); vis[sr][sc][p]=true; while(!q.empty()){ pos tp=q.front();q.pop(); //reach in time if(tp.r==er&&tp.c==ec&&tp.s<=t)return tp.s for(int i=0;i<4;i++){ int nr=tp.r+dr[i],nc=tp.c+dc[i]; if(nr<1||nr>n||nc<1||nc>m||maze[nr][nc]=='#')continue; //FLY if(tp.p>0&&!vis[nr][nc][tp.p-1]){ q.push(pos(nr,nc,tp.p-1,tp.s+1)); vis[nr][nc][tp.p-1]=true; } //WALK if(maze[tp.r][tp.c]=='@'||maze[nr][nc]=='@')continue;//CAN`T WALK if(!vis[nr][nc][tp.p]){ q.push(pos(nr,nc,tp.p,tp.s+2)); vis[nr][nc][tp.p]=true; } } } return -1; } int main(){ int cas=1; while(scanf("%d%d%d%d",&n,&m,&t,&p)!=EOF){ for(int i=1;i<=n;i++){ scanf("%s",maze[i]+1); for(int j=1;j<=m;j++){ if(maze[i][j]=='Y')sr=i,sc=j; if(maze[i][j]=='L')er=i,ec=j; } } int r=bfs(); printf("Case %d:\n",cas++); if(r==-1)printf("Poor Yifenfei, he has to wait another ten thousand years.\n"); else printf("Yes, Yifenfei will kill Lemon at %d sec.\n",r); } return 0; }