after与迷宫

after与迷宫

题目分析：

1.走过F/M房间就不能再走M/F的房间，所以进行两次bfs搜索，取最小的步数
2.分两种情况走：
一：F当普通房间走，但是这时候不能走M；二：M当普通房间走，同样不能走F
3.怎么去就怎么回来，步数*2

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
#define eps 1e-6

const int N = 1e3 + 10;

int t,n,m;
char g[N][N];
bool st[N][N];
int d[N][N];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int xa,ya,xb,yb;

int bfs(){
    queue<pii > q;
    mm(d,inf);
    d[1][1] = 0;
    q.push({1,1});
    while(!q.empty()){
        pii t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i ++ ){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 1 || a > n || b < 1 || b > m) continue;
            if(d[a][b] != inf || g[a][b] == 'M' || g[a][b] == '*') continue;
            d[a][b] = d[x][y] + 1;
            q.push({a,b}); 
        }
    }
    int m1 = d[xb][yb];
    q = queue<pii>();
    mm(d,inf);
    d[1][1] = 0;q.push({1,1});
    while(!q.empty()){
        pii t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i ++ ){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 1 || a > n || b < 1 || b > m) continue;
            if(d[a][b] != inf || g[a][b] == 'F' || g[a][b] == '*') continue;
            d[a][b] = d[x][y] + 1;
            q.push({a,b}); 
        }
    }
    int m2 = d[xb][yb];
    return min(m1,m2);
}
int main() {
    cin >> t;
    while(t -- ){
        cin >> n >> m >> xb >> yb;
        xa = ya = 1;
        for(int i = 1; i <= n; i ++ ){
            for(int j = 1; j <= m; j ++ ){
                cin >> g[i][j];
            }
        }
        int ans = bfs();
        if(ans == inf) cout<<"IMPOSSIBLE\n";
        else cout<<ans * 2<<endl;
    }    
    return 0;
}