P1374 进攻幽暗城题解

wzmzmhk · 2021-08-24 02:11:26 · 题解

upd ：感谢卑微蒟蒻上线的指正，修改了一个错别字。

题目传送门
博客食用更佳

Part 0 前言

这应该是本蒟蒻暑假的最后一篇题解了吧。

讨论区中很多人说该题目的 x 和 y 给反了，甚至扯到港澳与大陆的原因，其实不然，只是 OI 与数学的习惯不同。在这一题的图中即有说明，其 x 代表纵轴，y 代表横轴。在本题中，你只要记住： x 管的永远是第几行，y 管的永远是第几列。

Part 1 题目大意

给定小 A 、萨尔以及恐惧魔王的位置，要求求出小 A 遇到魔王的最短时间。
萨尔和恐惧魔王的运动方式都是固定不动的。
小 A 只可以在距离萨尔 d 距离内或距离萨尔 d 距离外连续 s 秒。

Part 2 主要思路

常见的 bfs 题，模拟萨尔、小 A 与恐惧魔王的位置即可，当萨尔与恐惧魔王位置相同时，输出答案即可。

具体过程与细节：

用数组flag打标记，确定当前位置是否走过，如走过就不再添加新节点（这一点不用我多说了吧）。
对于每一次移动，首先确定恐惧魔王与萨尔的位置（因为他们的位置是绝对的），再与小 A 的位置进行比较。
在添加新的节点时，也要判断小 A 与魔王的位置（即本题的 bfs 要进行两次特判），因为小 A 既有可能在移动之前魔王就自己送上门来，也有可能是移动后与魔王相遇。
在结构体中增加一个变量t1，用来记录小 A 超出萨尔光环的时间，如果已经在光环内，立马将t1赋值为 0，否则t1增加 1。

Part 3 分块步骤

建立一个结构体，储存三人（~~魔王算人？~~）的坐标以及已用的时间和小 A 超出光环的时间（dem为魔王的缩写）。

struct coord {
    int Ax, Ay;//小A的坐标
    int sx, sy;//萨尔的坐标
    int demx, demy;//魔王的坐标
    int t;//已用时间
    int t1 = 0;//超出光环的时间（默认为0）
};

用两个函数分别模拟萨尔和魔王的路线：

coord Sal(coord x, int s) {
    if (s == 0)
        return x;
    else if (s == 1) {
        int ux = x.sx - 1, uy = x.sy;
        if (ux <= 0 || c[ux][uy] == '1')
            return x;
        x.sx = ux;
        return x;
    }//向上走
    else if (s == 2) {
        int ux = x.sx + 1, uy = x.sy;
        if (ux > n || c[ux][uy] == '1')
            return x;
        x.sx = ux;
        return x;
    }//向下走
    else if (s == 3) {
        int ux = x.sx, uy = x.sy - 1;
        if (uy <= 0 || c[ux][uy] == '1')
            return x;
        x.sy = uy;
        return x;
    }//向左走
    else {
        int ux = x.sx, uy = x.sy + 1;
        if (uy > m || c[ux][uy] == '1')
            return x;
        x.sy = uy;
        return x;
    }//向右走
}

由于恐惧魔王与萨尔的方式几乎一模一样，此处就不再赘述。

用普通的 bfs 模拟即可，要注意进行两次特判：

int s1 = S[(l.t - 1) % S.size()] - '0';//确定萨尔的数字（即移动方式）
int m1 = M[(l.t - 1) % M.size()] - '0';//确定魔王的数字（即移动方式）
u = Sal(l, s1), u = Dem(l, m1);
if (u.Ax == u.demx && u.Ay == u.demy) {
    cout << u.t;
    return 0;
}//魔王移动后的特判
for (int i = 0; i < 4; i++) {
    int ux = l.Ax + dx[i], uy = l.Ay + dy[i];//用dx和dy模拟上下左右四个方向
    if (ux <= 0 || uy <= 0 || ux > n || uy > m || c[ux][uy] == '1' || flag[ux][uy] == true)
        continue;//如果超出地图范围或该区域是墙或已经走过，就不能再走了
    u.Ax = ux, u.Ay = uy;
    if (dis(u) <= d) {//dis表示小A与萨尔的距离
        flag[ux][uy] = true;
        coord uu = u;
        uu.t1 = 0;//在光环内要及时清零
        q.push(uu);//添加新的节点
        if (uu.Ax == uu.demx && uu.Ay == uu.demy) {
            cout << uu.t;
            return 0;
        }//小A移动后的特判
    }
    else if (l.t1 + 1 <= s) {//若dis(u)>d，则看看时间是否超出s，若未超出即可添加新节点
        coord uu = u;
        uu.t1 = l.t1 + 1;//超出的时间要加1
        q.push(uu);//添加新的节点
        flag[ux][uy] = true;//打标记
        if (uu.Ax == uu.demx && uu.Ay == uu.demy) {
            cout << uu.t;
            return 0;
        }//小A移动后的特判
    }
}

Part 4 完整代码

AC code（含详细注释）：

#include <iostream>
#include <cmath>
#include <string>
#include <queue>
using namespace std;
#define y1 y_
#define x1 x_
//typedef long long int;
const int maxn = 55;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
bool flag[maxn][maxn];
struct coord {
    int Ax, Ay;//小A的坐标
    int sx, sy;//萨尔的坐标
    int demx, demy;//魔王的坐标
    int t;//已用时间
    int t1 = 0;//超出光环的时间（默认为0）
};
queue<coord> q;
char c[maxn][maxn];
int n, m, s, d;
double dis(coord a) {//距离函数
    double d = sqrt(pow(a.Ax - a.sx, 2) + pow(a.Ay - a.sy, 2));
    return d;
}
coord Sal(coord x, int s) {
    if (s == 0)
        return x;
    else if (s == 1) {
        int ux = x.sx - 1, uy = x.sy;
        if (ux <= 0 || c[ux][uy] == '1')
            return x;
        x.sx = ux;
        return x;
    }//向上走
    else if (s == 2) {
        int ux = x.sx + 1, uy = x.sy;
        if (ux > n || c[ux][uy] == '1')
            return x;
        x.sx = ux;
        return x;
    }//向下走
    else if (s == 3) {
        int ux = x.sx, uy = x.sy - 1;
        if (uy <= 0 || c[ux][uy] == '1')
            return x;
        x.sy = uy;
        return x;
    }//向左走
    else {
        int ux = x.sx, uy = x.sy + 1;
        if (uy > m || c[ux][uy] == '1')
            return x;
        x.sy = uy;
        return x;
    }//向右走
}
coord Dem(coord x, int m1) {
    if (m1 == 0)
        return x;//原地不动
    else if (m1 == 1) {
        int ux = x.demx - 1, uy = x.demy;
        if (ux <= 0 || c[ux][uy] == '1')
            return x;
        x.demx = ux;
        return x;
    }//向上走
    else if (m1 == 2) {
        int ux = x.demx + 1, uy = x.demy;
        if (ux > n || c[ux][uy] == '1')
            return x;
        x.demx = ux;
        return x;
    }//向下走
    else if (m1 == 3) {
        int ux = x.demx, uy = x.demy - 1;
        if (uy <= 0 || c[ux][uy] == '1')
            return x;
        x.demy = uy;
        return x;
    }//向左走
    else {
        int ux = x.demx, uy = x.demy + 1;
        if (uy > m || c[ux][uy] == '1')
            return x;
        x.demy = uy;
        return x;
    }//向右走
}
int main() {
    cin >> n >> m >> s >> d;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            do
                c[i][j] = getchar();
            while (c[i][j] == ' ' || c[i][j] == '\n' || c[i][j] == '\r');//防止读入空格、回车
        }
    }
    int x, y, x1, y1;
    cin >> x >> y >> x1 >> y1;
    flag[x][y] = true;
    string S, M;
    getline(cin, S);//getline的坑点，会读入上一行的回车
    getline(cin, S);
    getline(cin, M);
    coord l;
    l.Ax = l.sx = x, l.Ay = l.sy = y;
    l.demx = x1, l.demy = y1;
    l.t = 0;
    q.push(l);
    while (!q.empty()) {
        coord l = q.front();
        q.pop();
        l.t++;
        coord u;
        int s1 = S[(l.t - 1) % S.size()] - '0';//确定萨尔的数字（即移动方式）
        int m1 = M[(l.t - 1) % M.size()] - '0';//确定魔王的数字（即移动方式）
        u = Sal(l, s1), u = Dem(l, m1);
        if (u.Ax == u.demx && u.Ay == u.demy) {
            cout << u.t;
            return 0;
        }//魔王移动后的特判
        for (int i = 0; i < 4; i++) {
            int ux = l.Ax + dx[i], uy = l.Ay + dy[i];//用dx和dy模拟上下左右四个方向
            if (ux <= 0 || uy <= 0 || ux > n || uy > m || c[ux][uy] == '1' || flag[ux][uy] == true)
                continue;//如果超出地图范围或该区域是墙或已经走过，就不能再走了
            u.Ax = ux, u.Ay = uy;
            if (dis(u) <= d) {//dis表示小A与萨尔的距离
                flag[ux][uy] = true;
                coord uu = u;
                uu.t1 = 0;//在光环内要及时清零
                q.push(uu);//添加新的节点
                if (uu.Ax == uu.demx && uu.Ay == uu.demy) {
                    cout << uu.t;
                    return 0;
                }//小A移动后的特判
            }
            else if (l.t1 + 1 <= s) {//若dis(u)>d，则看看时间是否超出s，若未超出即可添加新节点
                coord uu = u;
                uu.t1 = l.t1 + 1;//超出的时间要加1
                q.push(uu);//添加新的节点
                flag[ux][uy] = true;//打标记
                if (uu.Ax == uu.demx && uu.Ay == uu.demy) {
                    cout << uu.t;
                    return 0;
                }//小A移动后的特判
            }
        }
    }
    return 0;
}

另外强烈推荐无注释版。

Part 5 后记

此题的数据真的过水，几乎没有一个大的数据。总之，我们解决了一道超恶心、多细节的广搜题。如有错误，欢迎评论或私信指出。

P1374 进攻幽暗城 题解