真是头大。老是犯些超级低级的错误;
数组我存的时候下标写的是 1 开始,
我用check函数判断的时候写的确实 a.x<0||b.x<0
一个错误找一天。
唉。。。说多了都是泪;
发现错了就重新拍代码,拍了还是犯这样的错; 绝对是太粗心了;
///////////////////////////////////
********************
思路:
对每个点 进行走路和飞行的判断和遍历;
visit 三位数组 存放当前点 当前magic是否遍历过。
********************
/////////////////////////////////
/* *Author ID:fuqiang11 *Problem ID:HDU 2653 *Submit Time:2013/7/26 *Algorithm :BFS + priority_queue */ #include <iostream> #include <cstdio> #include <string> #include <queue> #include <cstring> using namespace std; #define maxn 82 int N,M,T,P; struct point { int x; int y; int t; int p; friend bool operator < (point a, point b) { return a.t > b.t; } }st,ed; char maze[maxn][maxn]; int visit[maxn][maxn][maxn]; int xx[] = {0,0,1,-1}; int yy[] = {1,-1,0,0}; bool check(point a) { if(a.x<1||a.y<1||a.x>N||a.y>M||maze[a.x][a.y]=='#'||visit[a.x][a.y][a.p]) return false; return true; } priority_queue <point> q; void BFS() { while(!q.empty()) //release queue q.pop(); q.push(st); point a,b; while(!q.empty()) { a = q.top(); q.pop(); if(a.t > T) break; if(a.x==ed.x && a.y==ed.y) { printf("Yes, Yifenfei will kill Lemon at %d sec.\n",a.t); return ; } for(int i = 0; i < 4; i++) { b.x = a.x + xx[i]; b.y = a.y + yy[i]; b.t = a.t; b.p = a.p; if(check(b)) { if(maze[a.x][a.y]!='@' && maze[b.x][b.y]!='@') //能走能飞的情况 选择走 { visit[b.x][b.y][b.p] = 1; b.t += 2; q.push(b); b.t -= 2; } if(!visit[b.x][b.y][b.p-1] && b.p>0)//选择飞 { b.p -= 1; b.t += 1; visit[b.x][b.y][b.p] = 1; q.push(b); } } } }//end while printf("Poor Yifenfei, he has to wait another ten thousand years.\n"); return ; } int main() { int Case = 1; while(scanf("%d%d%d%d",&N,&M,&T,&P)!=EOF) { int i,j; for (i=1;i<=N;i++) scanf("%s",maze[i]+1); for (i=1;i<=N;i++) { for (j=1;j<=M;j++) { if (maze[i][j]=='Y') {st.x=i; st.y=j;} if (maze[i][j]=='L') {ed.x=i; ed.y=j;} } } printf("Case %d:\n",Case++); memset(visit,0,sizeof(visit)); st.p = P; st.t = 0; visit[st.x][st.y][st.p] = 1; BFS(); } }