传送门:百练4116:拯救行动
题解:因为骑士杀死守卫会耗费时间,所以要用优先队列来维护步数。
收获:学会了无参构造方法的使用。
代码1:注意用无参构造方法的话,就不能再构造结构体类型的变量啦,例如,Maze tmp;这样的就不可以。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=210;
char mp[maxn][maxn];
int n,m,x1,y1;
int dir[4][2]={-1,0,1,0,0,-1,0,1},vis[maxn][maxn]; //上下左右struct Maze{int x,y;int step;bool operator<(const Maze &m)const{return step>m.step;}Maze(int x,int y,int s): x(x),y(y),step(s){}
};int bfs(int x,int y){priority_queue<Maze > pq;pq.push(Maze(x,y,0));while(!pq.empty()){int tmp_x=pq.top().x;int tmp_y=pq.top().y;int tmp_step=pq.top().step;pq.pop();//cout<<"tmp.x="<<tmp.x<<",tmp.y="<<tmp.y<<",tmp.step="<<tmp.step<<",mp[tmp.x][tmp.y]="<<mp[tmp.x][tmp.y]<<endl;//if(mp[tmp.x][tmp.y]=='a') return tmp.step;for(int i=0;i<4;i++){int dx=tmp_x+dir[i][0];int dy=tmp_y+dir[i][1];if(dx<0||dy<0||dx>=n||dy>=m) continue;if(!vis[dx][dy]){vis[dx][dy]=1;if(mp[dx][dy]=='@'){pq.push(Maze(dx,dy,tmp_step+1));}else if(mp[dx][dy]=='x'){pq.push(Maze(dx,dy,tmp_step+2));}else if(mp[dx][dy]=='a'){return tmp_step+1;}}}}return -1;
}int main(){int s;scanf("%d",&s);while(s--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%s",mp[i]);}int x=-1,y;for(int i=0;i<n;i++){if(x!=-1) break;for(int j=0;j<m;j++){if(mp[i][j]=='r'){x=i;y=j;}}}memset(vis,0,sizeof(vis));int ans=bfs(x,y);if(ans==-1) printf("Impossible\n");else printf("%d\n",ans);}return 0;
}
代码2:不用无参构造方法,
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=210;
char mp[maxn][maxn];
int n,m,x1,y1;
int dir[4][2]={-1,0,1,0,0,-1,0,1},vis[maxn][maxn]; //上下左右struct Maze{int step;int x,y;bool operator<(const Maze &m)const{return step>m.step;}
}tmp,nxt;int bfs(int x,int y){priority_queue<Maze > pq;tmp.x=x;tmp.y=y;tmp.step=0;pq.push(tmp);while(!pq.empty()){tmp=pq.top();pq.pop();//cout<<"tmp.x="<<tmp.x<<",tmp.y="<<tmp.y<<",tmp.step="<<tmp.step<<",mp[tmp.x][tmp.y]="<<mp[tmp.x][tmp.y]<<endl;//if(mp[tmp.x][tmp.y]=='a') return tmp.step;for(int i=0;i<4;i++){int dx=tmp.x+dir[i][0];int dy=tmp.y+dir[i][1];if(dx<0||dy<0||dx>=n||dy>=m) continue;nxt.x=dx;nxt.y=dy;if(!vis[dx][dy]){vis[dx][dy]=1;if(mp[dx][dy]=='@'){nxt.step=tmp.step+1;//cout<<"nxt.x="<<nxt.x<<",nxt.y="<<nxt.y<<",nxt.step="<<nxt.step<<",mp[nxt.x][nxt.y]="<<mp[nxt.x][nxt.y]<<endl;pq.push(nxt);}else if(mp[dx][dy]=='x'){nxt.step=tmp.step+2;//cout<<"nxt.x="<<nxt.x<<",nxt.y="<<nxt.y<<",nxt.step="<<nxt.step<<",mp[nxt.x][nxt.y]="<<mp[nxt.x][nxt.y]<<endl;pq.push(nxt);}else if(mp[dx][dy]=='a'){return tmp.step+1;}}}}return -1;
}int main(){int s;scanf("%d",&s);while(s--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%s",mp[i]);}int x=-1,y;for(int i=0;i<n;i++){if(x!=-1) break;for(int j=0;j<m;j++){if(mp[i][j]=='r'){x=i;y=j;}}}memset(vis,0,sizeof(vis));int ans=bfs(x,y);if(ans==-1) printf("Impossible\n");else printf("%d\n",ans);}return 0;
}