非常郁闷的--hdu2653（有心的朋友帮帮忙）

这个题真的非常郁闷，错了一下午、、、、、

明明思路非常的正确，怎么修改就是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;	
}