P1374题解

· · 题解

题目大意

思路

显然，可以用 bfs 模拟这三个人的移动，当 小 A 和恐惧魔王在相同位置时即可输出所需时间，当然各位 dalao 也可用迭代加深搜索做，但本蒟蒻不会。

代码实现

由于我们要存三个人的状态，所以细节还是蛮多的。

  1. 我们定义一个队列存储每个人的位置，小 A 距离萨尔超过 d 距离的时间 ti 以及走到当前位置需要的时间 t 。（ti 是个变量名）

  2. 因为萨尔和恐惧魔王的移动方式固定，所以可以直接将字符串转换为数字，分别记录两人一次规则运动的步数即字符串的长度为 size_1 和 size_2 ，在 bfs 时可以直接 t \bmod size_1 和 t \bmod size_2 求出萨尔和恐惧魔王下一步的方向。

  3. 当小 A 距萨尔不超过 d 距离时 ti 值赋为 0 ，这样小 A 重新进入萨尔的光环范围内时 ti 就可以及时更新，当两人距离大于 d 时 ti + 1 ，当 ti > s 时就直接跳过。

  4. 可以专门写个函数来求小 A 与萨尔的距离，记得一定要用 double。

  5. 剩下的操作就是常规 bfs 了，数据很水，所以能过。

代码

#include <bits/stdc++.h>
using namespace std;
int tot ,cnt;
int a[1001][1001];
int n , m ,s , d;
int sx ,sy ,zx ,zy;
int hu[10001];
int mo[10001];
string s1 ,s2;
const double eps=1e-6;
int dx[6] = {0 ,-1 ,1 ,0 ,0 ,0};
int dy[6] = {0 ,0 ,0 ,-1 ,1 ,0};
struct node{
    int ax ,ay;
    int sx ,sy;
    int mx ,my;
    int t ,ti;
};
queue <node> q;
bool Saber(int x,int xx,int y,int yy){
    double s = sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy)) + eps;
    return s <= d * 1.0;
}
bool check(int x,int y){
    return x > 0 && x <= n && y > 0 && y <= m && !a[x][y];
}
void bfs(){
    q.push((node){sx ,sy ,sx ,sy ,zx ,zy, 0, 0});
    while(q.size()){
        node nw = q.front();q.pop();
        if(nw.ax == nw.mx && nw.ay == nw.my){
            cout << nw.t;exit(0);
        }
        nw.t ++;
        int la = nw.t % tot;if(la == 0)la = tot;
        int lb = nw.t % cnt;if(lb == 0)lb = cnt;
        nw.sx += dx[hu[la]],nw.sy += dy[hu[la]];
        if(!check(nw.sx,nw.sy))nw.sx -= dx[hu[la]],nw.sy -= dy[hu[la]]; 
        nw.mx += dx[mo[lb]],nw.my += dy[mo[lb]]; 
        if(!check(nw.mx,nw.my))nw.mx -= dx[mo[lb]],nw.my -= dy[mo[lb]];
        for(int i = 1;i <= 5;i ++){
            int fx = nw.ax + dx[i];
            int fy = nw.ay + dy[i];
            if(!check(fx ,fy))continue;
            if(Saber(fx , nw.sx ,fy ,nw.sy) > d){
                if(nw.ti + 1 > s)continue;
                nw.ti ++;
            }
            else nw.ti = 0;
            q.push((node){fx ,fy ,nw.sx ,nw.sy ,nw.mx ,nw.my ,nw.t ,nw.ti});
        }
    }   
}
int main(){
       cin >> n >> m >> s >> d;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            char ch;cin >> ch;
            if(ch == '1')a[i][j] = 1;
        }
    }
    cin >> sx >> sy >> zx >> zy;
    cin >> s1 >> s2;
    for(int i = 0;i < s1.size();i ++){
        hu[++ tot] = s1[i] - '0';
    }
    for(int i = 0;i < s2.size();i ++){
        mo[++ cnt] = s2[i] - '0';
    }
    bfs();
}