题解 P3855 【[TJOI2008]Binary Land】

· · 题解

前言

本来想刷DP题刷到了这个（为什么标签里面有动态规划？），权当复习一下Bfs吧。

前面的dalao吊打我，我的代码比较繁琐emm。

题解

熟练Bfs的同学应该不要多讲吧，思路简单

\text{Bfs前准备}

定义状态 Node

xG,yG,xM,yM,step; //表示G与M的位置,移动步数，看成一个整体

自然就有了四维的vis数组 vis[xG][yG][xM][yM]，来表示这个状态是否经历过。

\text{Bfs}

后记

关于游戏视频 ---> bilibili传送门 （这个游戏看起来还蛮好玩）

祝你AC （其实这道题不是很水qwq）

\texttt{Code} 
#include<iostream>
#include<cstdio>
#include<queue>
#define N 37
using namespace std;
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
int n,m,XG,YG,XM,YM,ans=-1;
char map[N][N];
bool vis[N][N][N][N];
struct Node {
    int xG,yG;
    int xM,yM;
    int step;
};
queue<Node> q;
//  修改操作 （入队列，标记） 
inline void update(int x1,int y1,int x2,int y2,int step) {
    q.push((Node){x1,y1,x2,y2,step});
    vis[x1][y1][x2][y2] = 1;
}
//  判断是否能走 
inline bool check(int x1,int y1,int x2,int y2) {
    if(x1>=1&&x1<=n&&y1>=1&&y1<=m && x2>=1&&x2<=n&&y2>=1&&y2<=m)
        if(map[x1][y1]!='X' && map[x2][y2]!='X' && !vis[x1][y1][x2][y2])
            return 1;
    return 0;
}
//  判断是否到终点 
inline bool result(int x1,int y1,int x2,int y2) {
    if(map[x1][y1]=='T' && map[x2][y2]=='T')
        return 1;
    return 0;
}
//  一次操作 
inline bool work(int nx1,int ny1,int nx2,int ny2,int step)
{
    if(result(nx1,ny1,nx2,ny2))  {
        ans = step + 1;
            return 1;
        }
    if(check(nx1,ny1,nx2,ny2))  
        update(nx1,ny1,nx2,ny2,step+1);
    return 0;
}
void Bfs()
{
    update(XG,YG,XM,YM,0);
    while(!q.empty())
    {
        Node now = q.front(); q.pop();
//      printf("OK  ");
//      printf("xG=%d,yG=%d  xM=%d,yM=%d ,step=%d\n",now.xG,now.yG,now.xM,now.yM,now.step);
        for(int i=0;i<2;++i)
        {
            int nx1 = now.xG + dx[i] ,ny1 = now.yG + dy[i];
            int nx2 = now.xM + dx[i] ,ny2 = now.yM + dy[i];
        if(map[nx1][ny1] == '#') nx1=now.xG ,ny1=now.yG;    //挡住不走 
        if(map[nx2][ny2] == '#') nx2=now.xM ,ny2=now.yM;
            if(work(nx1,ny1,nx2,ny2,now.step)) return ;
        }
        int nx1,ny1,nx2,ny2;
//      往右走 G左，M右 
        nx1 = now.xG + dx[2] ,ny1 = now.yG + dy[2];
        nx2 = now.xM + dx[3] ,ny2 = now.yM + dy[3];
        if(map[nx1][ny1] == '#') nx1=now.xG ,ny1=now.yG;    //挡住不走 
        if(map[nx2][ny2] == '#') nx2=now.xM ,ny2=now.yM;
        if(work(nx1,ny1,nx2,ny2,now.step)) return ;
//      往左走 G右，M左 
        nx1 = now.xG + dx[3] ,ny1 = now.yG + dy[3];
        nx2 = now.xM + dx[2] ,ny2 = now.yM + dy[2];
        if(map[nx1][ny1] == '#') nx1=now.xG ,ny1=now.yG;    //挡住不走 
        if(map[nx2][ny2] == '#') nx2=now.xM ,ny2=now.yM;
        if(work(nx1,ny1,nx2,ny2,now.step)) return ;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            cin >> map[i][j];
            if(map[i][j] == 'G') XG=i ,YG=j;
            if(map[i][j] == 'M') XM=i ,YM=j; 
        }
    Bfs();
    if(ans == -1) printf("no\n");
    else printf("%d\n",ans);
    return 0; 
}