链接：https://ac.nowcoder.com/acm/problem/14608 来源：牛客网
after的算法书的遗落在一个叫做AIJ的迷宫中了，这个迷宫有N*M个房间，迷宫的入口为(1，1)，算法书遗落在(r，c)。迷宫中的房间有四种状态：空房间、无法进入的房间、有墨菲斯托存在的房间和有莉莉丝存在的房间。墨菲斯托会否定一切，而莉莉丝会诱惑人做一种叫做YK的活动。after是一个意志薄弱的人，他遇到了墨菲斯托和莉莉丝之后，便会变成眼神空洞的超级YK机器人。after每步可以从他当前的房间走至上下左右四个房间的其中一个房间。after害怕变成超级YK机器人，所以要尽快拿到算法书然后从入口逃离。问after最少需要走多少步才可以在不变成超级YK机器人的情况下从入口出发取回算法书并逃离迷宫？
思路:迷宫取书利用的就是bfs的思想afetr所在的位置就是(1,1) 如果遇到F就把它标记成‘.’ 或者遇见M就把也标记成’.’(其他的原样放入到s1数组)然后和可走房间一样 vis[i][j]表示已经走过不能重复再走 首先我是这样分析的第一次走只能遇见M在起点出发看他能否走通迷宫取到书籍的话就直接返回走的步数，将返回的数返回a1中，然后将vis全部初始化为0，第二次只会遇见F通过bfs返回一个值给a2 付过两次的值为负值 就不行 如果a1 a2不同为负值就取最大的2 因为他的路径是来回的，如果a1 a2都大于0就取最小的的最为最优步数记住2因为他是一个来回。
#include #include #include #include <string.h> #include using namespace std; struct Node{ int x,y; int step; }qq,zz;
int xx[]={-1,1,0,0}; int yy[]={0,0,-1,1}; int vis[1005][1005]; char s1[1005][1005],s[1005][1005]; int n,m,r,c; int bfs(int qx,int qy,int zx,int zy){ queue q; Node qq; qq.x=1;qq.y=1;qq.step=0; q.push(qq); vis[1][1]=1; while(!q.empty()){ Node now=q.front(); q.pop(); if(now.xzx&&now.yzy){ return now.step; } for(int i=0;i<4;i++){ qq.x=now.x+xx[i]; qq.y=now.y+yy[i]; if(qq.x>0&&qq.y>0&&qq.x<=n&&qq.y<=m&&s1[qq.x][qq.y]==’.’&&!vis[qq.x][qq.y]){
vis[qq.x][qq.y]=1; qq.step=now.step+1; q.push(qq); } } } return -1;}
int main(){ int t; cin>>t; while(t–){ cin>>n>>m>>r>>c; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>s[i][j]; if(s[i][j]‘F’){ s1[i][j]=’.’; }else{ s1[i][j]=s[i][j]; } } } memset(vis,0,sizeof(vis)); int a1=bfs(1,1,r,c); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s[i][j]‘M’){ s1[i][j]=’.’; }else{ s1[i][j]=s[i][j]; } } } memset(vis,0,sizeof(vis)); int a2=bfs(1,1,r,c); if(a1==-1&&a2==-1){ cout<<“Impossible”<<endl;
}else if(a1<0||a2<0){ cout<<max(a1,a2)*2<<endl; }else if(a1>0&&a2>0){ cout<<min(a1,a2)*2<<endl; } }}
