题解 | #after与迷宫#

题意：起点(1,1)，终点(r,c)。路径上不能同时出现M和F，但是可以出现其中一种或不出现。

然后就是一个bfs裸题，从起点bfs到终点，得到res后乘二就是来回的路径长度。

对于M和F两种情况，可以用一个字符k来临时记录当前bfs是哪一种可行，然后跑就是了。

推广到有3,4,5...k种不一样的字符。可以用一个string去存临时可行的字符，遍历string，对于每一个可行字符跑一遍bfs就算成功。

好思路，下次出题就出这个，不过这题的题面很明显level不是很高（乐）

直接贴代码吧，可以学学bfs板子和怎么去check

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,m,r,c,ans1,ans2;
char mp[maxn][maxn],k;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool vis[maxn][maxn];
struct node{int x,y,z;};
bool check(int x,int y)
{
    if(1<=x&&x<=n&&1<=y&&y<=m)//界内
        if(mp[x][y]=='.'||mp[x][y]==k)//能走
            if(!vis[x][y])//没走过
               return true;
    return false;
}
int bfs()
{
    queue<node> q;
    q.push({1,1,0});//添加起点
    while(q.size())//队列非空
    {
        int x=q.front().x;
        int y=q.front().y;
        int z=q.front().z;
        q.pop();//提取队首且pop
        if(x==r&&y==c)//到达终点
            return z;//返回步数
        for(int i=0;i<4;i++)//遍历四个方向
        {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(check(tx,ty))//合法步
            {
                vis[tx][ty]=true;//标记走过状态
                q.push({tx,ty,z+1});//添加进队列
            }
        }
    }
    return 0;
}
void solve()
{
    cin>>n>>m>>r>>c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    
    if(r==1&&c==1)//特判0
    {
        cout<<0<<endl;
        return ;
    }
    
    int ans,ans1=0,ans2=0;
    
    k='F';//假设F可以走
    memset(vis,0,sizeof vis);
    ans1=bfs();
    k='M';//假设M可以走
    memset(vis,0,sizeof vis);
    ans2=bfs();
    
    if(ans1==0&&ans2==0)
        puts("IMPOSSIBLE");
    else if(ans1==0)
        cout<<2*ans2<<endl;
    else if(ans2==0)
        cout<<2*ans1<<endl;
    else
        cout<<2*min(ans1,ans2)<<endl;
    return;
}
int main()
{
    int t;
    for(cin>>t;t--;solve());
    return 0;
}