# after and labyrinth-NC14608 (twice bfs)

After's algorithm book is left in a maze called AIJ. This maze has N*M rooms. The entrance of the maze is (1,1), and the algorithm book is left in (r, c). The rooms in the maze have four states: empty rooms, inaccessible rooms, rooms with Mephisto and rooms with Lilith. Mephisto would deny everything, while Lilith would tempt people to do an activity called YK. After is a weak willed person. After he meets Mephisto and Lilith, he will become a super YK robot with empty eyes. After each step can go from his current room to one of the four rooms up, down, left and right. After is afraid of becoming a super YK robot, so you should get the algorithm book as soon as possible and escape from the entrance. How many steps does after need to take to get back the algorithm book from the entrance and escape the maze without becoming a super YK robot?

Enter Description:
A positive integer t (t<=10) in the first row indicates a total of T groups of data. For each group of data, the first row contains four positive integers n, m, R, C (1<=n, m<=1000; 1<=r<=n; 1<=c<=m). The next N lines, each with M characters, represent the state of the room, "." Indicates an empty room, "*" indicates an inaccessible room, "F" indicates a room with Mephisto, and "m" indicates a room with Lilith. Data guarantee (1, 1) is ".".
Output Description:
Output a row for each group of data, that is, the minimum number of steps to be taken after. If after cannot retrieve the algorithm book, output "IMPOSSIBLE" (without quotation marks).

Input:
1
4 4 4 3
...**
*F...
..
*M.F
Output:
14
Idea:
Because a path cannot have both F and M, use two bfs, one without M and the other without f, and finally take two smaller values.

### ① p.s.'s wrong idea at first

At first, I thought about using the structure to store whether the current road has passed F and M, but I ignored that bfs will mark the places that have passed. If the short road and the long road have a common part, if the short road has had f before, and the common part meets M, the short road will be invalid. However, at this time, the public nodes have been marked, so even if the conditions are met, the long road will not go on. For example: The red road is short but not enough. When the red road reaches m, it does not meet the meaning of the question, but the previous node of M (that is, the point above M) has been marked, so the blue road is blocked and the question is unsolved.

```#include<bits/stdc++.h>
#include<time.h>
#include<cctype>
#include<iostream>
#include<ostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define maxn 10000000
typedef long long ll;
const int INF=0x7fffffff;//2147483647
const int SUP=0x80000000;//-2147483648
#define loop(a,b,i) for(int i=a;i<b;i++)
#define loopx(a,b,i) for(int i=a;i<=b;i++)
#define lson (p<<1)
#define rson ((p<<1)|1)
#define mid ((l+r)>>1)
#define MAX 100005
char mapp;
int d;
int dir={1,0,-1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};
int n,m,r,c;
struct node
{
int x,y;
int f,m;//Does this road pass through F,M
int ans;
}now,nex;
queue<node>que;
//int judge(struct node no)
//{
//    return no.x>=1&&no.x<=n&&no.y>=1&&no.y<=m&&d[no.x][no.y]==0&&mapp[no.x][no.y]!='*'&&(no.f==0||no.m==0);
//}
int bfs(int x,int y)
{
memset(d,0,sizeof(d));
now.x=x;
now.y=y;
now.ans=0;
now.f=0;
now.m=0;
d[x][y]=1;
while(!que.empty())que.pop();
que.push(now);
while(!que.empty())
{
now=que.front();
que.pop();
if(now.x==r&&now.y==c)return now.ans;
for(int i=0;i<4;i++)
{
nex.x=now.x+dir[i];
nex.y=now.y+dir[i];
nex.ans=now.ans+1;
if(nex.x<1||nex.x>n||nex.y<1||nex.y>m)continue;
if(mapp[nex.x][nex.y]=='*'||d[nex.x][nex.y]==1)continue;
nex.f=now.f;
nex.m=now.m;
if(mapp[nex.x][nex.y]=='F')nex.f=1;
if(mapp[nex.x][nex.y]=='M')nex.m=1;
if(nex.f==1&&nex.m==1)continue;
d[nex.x][nex.y]=1;
que.push(nex);
//cout<<nex.x<<" "<<nex.y<<" "<<nex.ans<<endl;
}
}
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>>mapp[i][j];
int ans=bfs(1,1);
if(ans==-1)cout<<"IMPOSSIBLE"<<endl;
else cout<<ans*2<<endl;
}
return 0;
}

```

### ② Correct code

```#include<bits/stdc++.h>
#include<time.h>
#include<cctype>
#include<iostream>
#include<ostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define maxn 10000000
typedef long long ll;
const int INF=0x7fffffff;//2147483647
const int SUP=0x80000000;//-2147483648
#define loop(a,b,i) for(int i=a;i<b;i++)
#define loopx(a,b,i) for(int i=a;i<=b;i++)
#define lson (p<<1)
#define rson ((p<<1)|1)
#define mid ((l+r)>>1)
#define MAX 100005
char mapp;
char ma;
int d;
int dir={1,0,-1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};
int n,m,r,c;
struct node
{
int x,y;
int ans;
}now,nex;
queue<node>que;
//int judge(struct node no)
//{
//    return no.x>=1&&no.x<=n&&no.y>=1&&no.y<=m&&d[no.x][no.y]==0&&mapp[no.x][no.y]!='*'&&(no.f==0||no.m==0);
//}
int bfs(int x,int y)//Find the shortest circuit in the current diagram
{
memset(d,0,sizeof(d));
now.x=x;
now.y=y;
now.ans=0;
d[x][y]=1;
while(!que.empty())que.pop();
que.push(now);
while(!que.empty())
{
now=que.front();
que.pop();
if(now.x==r&&now.y==c)return now.ans;
for(int i=0;i<4;i++)
{
nex.x=now.x+dir[i];
nex.y=now.y+dir[i];
nex.ans=now.ans+1;
if(nex.x<1||nex.x>n||nex.y<1||nex.y>m)continue;
if(ma[nex.x][nex.y]=='*'||d[nex.x][nex.y]==1)continue;
d[nex.x][nex.y]=1;
que.push(nex);
//cout<<nex.x<<" "<<nex.y<<" "<<nex.ans<<endl;
}
}
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>>mapp[i][j];
for(int i=1;i<=n;i++)//Don't take F, take F as*
for(int j=1;j<=m;j++)
{
if(mapp[i][j]=='F')ma[i][j]='*';
else ma[i][j]=mapp[i][j];
}
int ans1=bfs(1,1);
for(int i=1;i<=n;i++)//Don't take M as*
for(int j=1;j<=m;j++)
{
if(mapp[i][j]=='M')ma[i][j]='*';
else ma[i][j]=mapp[i][j];
}
int ans2=bfs(1,1);
if(min(ans1,ans2)==-1)
{
if(max(ans1,ans2)==-1)cout<<"IMPOSSIBLE"<<endl;
else cout<<max(ans1,ans2)*2<<endl;//To return, multiply by 2
}
else cout<<min(ans1,ans2)*2<<endl;
}
return 0;
}

```

Tags: Algorithm bfs

Posted by cowboysdude on Mon, 30 May 2022 13:49:39 +0530