BFS+优先队列,这道题一见到时候就把我镇住了,这不是曹操传吗。。。。。。。。。。。。
#include<iostream>
#include<stdio.h> #include<queue> using namespace std; struct node { friend bool operator < (node n1,node n2) { return n1.level<n2.level; } int x; int y; int level; }; char battle[105][105];//正常 int map[105][105]; //加一 int fatherx[105][105]; //正常 int fathery[105][105]; //正常 int xx[4]={1,0,-1,0}; int yy[4]={0,1,0,-1}; int v,x,y; void print(int x,int y) { int i,j,m,n; for(i=x,j=y;i!=-1&&j!=-1;i=fatherx[m][n],j=fathery[m][n]) { //cout<<i+1<<" "<<j+1<<endl; if(battle[j][i]!='P'&&battle[j][i]!='Y') battle[j][i]='*'; m=j; n=i; } } void BFS() { priority_queue<node> q; node k; k.x=x; k.y=y; k.level=v; q.push(k); while(!q.empty()) { node k=q.top(); q.pop(); int i,j,r_mark=0;; for(i=0;i<4;i++) { node m; if(map[k.y+1+yy[i]][k.x+1+xx[i]]==0) { continue; } else if(map[k.y+1+yy[i]][k.x+1+xx[i]]==1&&k.level>=1) { fatherx[k.y+yy[i]][k.x+xx[i]]=k.x; fathery[k.y+yy[i]][k.x+xx[i]]=k.y; map[k.y+1+yy[i]][k.x+1+xx[i]]=0; int mark=0; for(j=0;j<4;j++) { if(map[k.y+1+yy[i]+yy[j]][k.x+1+xx[i]+xx[j]]==5) { mark=1; break; } } if(mark==0) { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=k.level-1; q.push(m); r_mark=1; } else { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=0; q.push(m); r_mark=1; } /* if(m.level==0) { printf("%d %d\n",m.x,m.y); }*/ } else if(map[k.y+1+yy[i]][k.x+1+xx[i]]==2&&k.level>=2) { fatherx[k.y+yy[i]][k.x+xx[i]]=k.x; fathery[k.y+yy[i]][k.x+xx[i]]=k.y; map[k.y+1+yy[i]][k.x+1+xx[i]]=0; int mark=0; for(j=0;j<4;j++) { if(map[k.y+1+yy[i]+yy[j]][k.x+1+xx[i]+xx[j]]==5) { mark=1; break; } } if(mark==0) { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=k.level-2; q.push(m); r_mark=1; } else { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=0; q.push(m); r_mark=1; } /* if(m.level==0) { printf("%d %d\n",m.x,m.y); }*/ } else if(map[k.y+1+yy[i]][k.x+1+xx[i]]==3&&k.level>=3) { fatherx[k.y+yy[i]][k.x+xx[i]]=k.x; fathery[k.y+yy[i]][k.x+xx[i]]=k.y; map[k.y+1+yy[i]][k.x+1+xx[i]]=0; int mark=0; for(j=0;j<4;j++) { if(map[k.y+1+yy[i]+yy[j]][k.x+1+xx[i]+xx[j]]==5) { mark=1; break; } } if(mark==0) { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=k.level-3; q.push(m); r_mark=1; } else { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=0; q.push(m); r_mark=1; } /* if(m.level==0) { printf("%d %d\n",m.x,m.y); }*/ } else if(map[k.y+1+yy[i]][k.x+1+xx[i]]==6&&k.level>=1) { fatherx[k.y+yy[i]][k.x+xx[i]]=k.x; fathery[k.y+yy[i]][k.x+xx[i]]=k.y; map[k.y+1+yy[i]][k.x+1+xx[i]]=0; int mark=0; for(j=0;j<4;j++) { if(map[k.y+1+yy[i]+yy[j]][k.x+1+xx[i]+xx[j]]==5) { mark=1; break; } } if(mark==0) { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=k.level-1; q.push(m); r_mark=1; } else { m.x=k.x+xx[i]; m.y=k.y+yy[i]; m.level=0; q.push(m); r_mark=1; } /* if(m.level==0) { printf("%d %d\n",m.x,m.y); }*/ } } /* cout<<"juzhenwei"<<endl; int h,l; for(h=0;h<7;h++) { for(l=0;l<8;l++) printf("%d ",map[h][l]); printf("\n"); } // cout<<q.top().level<<" "; // cout<<endl;*/ if(r_mark==0) print(k.x,k.y); } } int main() { int total_case,iii; scanf("%d",&total_case); for(iii=0;iii<total_case;iii++) { int n,m,i,j; memset(map,0,sizeof(map)); memset(fatherx,0,sizeof(fatherx)); memset(fathery,0,sizeof(fathery)); scanf("%d%d%d",&n,&m,&v); for(i=0;i<n;i++) scanf("%s",battle[i]); for(i=0;i<n;i++) for(j=0;j<m;j++) { if(battle[i][j]=='.') map[i+1][j+1]=1; else if(battle[i][j]=='T') map[i+1][j+1]=2; else if(battle[i][j]=='R') map[i+1][j+1]=3; else if(battle[i][j]=='Y') { y=i; x=j; map[i+1][j+1]==0; } else if(battle[i][j]=='E') map[i+1][j+1]=5; else if(battle[i][j]=='P') map[i+1][j+1]=6; } /*for(i=0;i<n;i++) printf("%s\n",battle[i]); /*for(i=0;i<n+2;i++) { for(j=0;j<m+2;j++) printf("%d ",map[i][j]); printf("\n"); }*/ fatherx[y][x]=-1; fathery[y][x]=-1; BFS(); for(i=0;i<n;i++) printf("%s\n",battle[i]); // cout<<fatherx[0][3]+1<<" "<<fathery[0][3]+1<<endl; printf("\n"); } }