开始做这题时没想到用优先队列,以为是用一个广搜就可以解决,样例过后提交wa,然后又读了一遍题,自己测试了几组数据,发现搜索时要从用时少的开始搜,才想到用优先队列,但是因为优先队列不是很了解,结果一直wa wa。。。又读了n遍题+测试n次还是不知道哪错了,无奈下把代码整理了一下,把priority_queue<zhang>q;放到调用的函数里面结果出乎意料的Ac了!
代码:
#include<stdio.h> #include<string.h> #include<queue> using namespace std; char s[303][303]; int sum,m,n,vis[303][303],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; struct zhang { int x,y,bu; friend bool operator<(const zhang &a,const zhang &b) { return a.bu > b.bu ; } }; void bfs(int x1,int y1) { priority_queue<zhang>q; zhang current,next; memset(vis,0,sizeof(vis)); int f=0,d; vis[x1][y1]=1; current.bu=0; current.x=x1; current.y=y1; q.push(current); while(!q.empty()) { if(f==1)break; current=q.top(); q.pop(); for(d=0;d<4;d++) { next.x=current.x+dx[d]; next.y=current.y+dy[d]; if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&!vis[next.x][next.y]&&s[next.x][next.y]!='S'&&s[next.x][next.y]!='R') { vis[next.x][next.y]=1; if(s[next.x][next.y]=='B') next.bu=current.bu+2; else if(s[next.x][next.y]=='E') next.bu=current.bu+1; else if(s[next.x][next.y]=='T') { f=1;sum=current.bu+1;break; } q.push(next); } } } } int main() { int i,j,x1,y1; while(scanf("%d%d",&n,&m)!=EOF) { sum=-1; if(n==0&&m==0)break; for(i=0;i<n;i++) { getchar(); for(j=0;j<m;j++) { scanf("%c",&s[i][j]); if(s[i][j]=='Y') { x1=i;y1=j; } } } bfs(x1,y1); printf("%d\n",sum); } return 0; }