真·保卫萝卜-526互联

这题数据标程锅了，但是既然对它付出了，纪念一下。听我说谢谢你_{，因为有你}，温暖了四季······

《地球Online》是一款很好玩的塔防类游戏。小B最近就迷上了这款游戏。然而小B又是一个很强势的人，他很不想玩游戏输掉，所以他想让你写一个程序帮忙算一下某一局游戏的结果和详细信息。小B已经知道了游戏的运行规则和相关信息，你能帮帮他吗?

游戏的相关信息:

1.地图:

游戏的地图是一个 \(n \times m\) 的矩阵，设左上角坐标为 \((1，1)\)。

地图以字符矩阵的形式给出，比如 \(n=m=5\) 的情况：

S1###
001##
#0###
#0002
###0T

矩阵中第 \(i\) 行第 \(j\) 列的字符表示 \((i,j)\) 的情况。不同的字符对应的情况如下:

#: 普通地图格点。
0: 怪物通过的路线。
1~9: 防御塔。
S: 怪物的生成点。
T: 你的基地，即游戏的目的要防止怪物进入基地。

输入数据保证地图合法，即地图上有且只有一个 S 和一个 T ， S 到 T 有且只有唯一的路线。

2.怪物:

小B会给出一个怪物的生成队列，表示怪物的出现顺序。

若队列不为空，则每一秒将会从队头取出一个新的怪物放在 \(\text{S}\) 处。

我们用两个整数来描述怪物的相关信息:

\(\text{blood}\): 怪物的血量。当血量小于等于 \(0\) 时怪物死亡，从地图上消失。
\(\text{speed}\): 怪物的移动速度。每回合怪物将会沿着行进路线向 \(\text{T}\) 移动 \(\text{speed}\) 个单位。如果 \(\text{speed}=0\) 那么怪物将被定在原地无法移动。如果移动后将超过 \(T\) 处，那么视为到达了 \(\text{T}\) 处。

3.防御塔:

整个地图上最多会出现 \(\text{t} ( 1\leq t\leq 9)\) 种不同的防御塔，用字符1~9在地图上表示。

为了简化题目，我们假定小 \(\text{B}\) 不会在游戏过程中建造新的防御塔。所有防御塔在开始前就已经建造好了。我们用三个整数来描述每种防御塔的相关信息:

\(\text{damage}\): 表示该防御塔击中怪物后将对怪物造成的伤害。
\(\text{distance}\): 表示该防御塔能攻击到的最远距离。如果怪物与塔之间的直线距离不超过 \(\text{distance}\) ，表示该塔可以攻击到该这个怪物。
\(\text{type}\): 表示该防御塔的攻击类型。
若 \(\text{type}=0\) 表示该防御塔为普通攻击类型，即对单个怪物造成伤害。
若 \(\text{type}=1\) 表示该防御塔为范围性伤害，在对当前瞄准的怪物造成伤害的同时还会对该怪物周围距离不超过 \(1\) 的怪物造成伤害。
若 \(\text{type}=2\) 表示该防御塔为直线型伤害，在攻击时将会生成一条连接该防御塔和当前瞄准的怪物的直线。直线可以向两端无限延伸，并且将对所有与直线距离不超过 \(1\) 的怪物造成伤害。值得注意的是，虽然直线能够打到很远处的怪物，但是这种防御塔必须在有怪物离它不超过 \(\text{distance}\) 时才能找到攻击目标发动攻击。
若 \(\text{type}=3\) 表示该防御塔为普通攻击类型，即对单个怪物造成伤害，并且会使命中的怪物的速度永久减少 1。但是减速效果在一个怪物身上最多只能生效一次，无法叠加。

为了防止歧义，我们定义防御塔选取目标的方式:

若当前有攻击目标，并且目标没有死亡、在攻击范围之内，那么将保持当前怪物作为目标。

若当前目标不合法(目标怪物死亡、超出攻击范围)或是没有攻击目标，将从攻击范围内的怪物中选取最靠前的一个(此处最靠前的定义为在怪物移动路径上里离 \(\text{T}\) 点最近)，若有多个则选取血量最少的一个，若还有多个则选取最早生成的一个。

为了简化题目，我们假定游戏为回合制，一秒为一个回合。对于每个回合，严格按照顺序有如下几个阶段:

怪物生成阶段:若队列不为空，则取出怪物生成队列队头处的怪物放在 \(\text{S}\) 处。
防御塔锁定阶段:所有防御塔按照规则选取目标。
防御塔攻击阶段:所有防御塔同时对自己的目标发动攻击。
伤害结算阶段:将所有怪物的血量减去所受的攻击力，并将死亡的怪物清除。
怪物移动阶段:地图上存在的怪物向前移动。
回合结束阶段:若某个怪物处于 \(\text{T}\) 处，则将该怪物移除并视为基地遭到一次攻击。

你的基地共有 \(10\) 点血量，每遭到一次攻击则血量减 \(1\) 。如果某回合结束后你的基地血量小于等于 \(0\) ，则游戏结束，小B失败。如果场上没有任何怪物并且怪物生成队列为空，那么游戏结束，小 \(\text{B}\) 胜利。输入数据保证不会有游戏无法结束的情况。

输入格式

第一行有两个整数 \(\text{n,m} (n,m\leq 10)\)，意义如题目中所述。

接下来的 \(\text{n}\) 行每行有一个长度为 \(\text{m}\) 的字符串,描述地图。

接下来一行有一个整数 \(\text{t}\) ，意义如题目中所述。

接下来 \(\text{t}\) 行，每行三个整数 \(\text{damage,distance,type}\) ，描述防御塔。

接下来一行有一个整数 \(\text{q} (q\leq 50)\) ，表示怪物生成队列的长度。

接下来 \(\text{q}\) 行，每行两个整数 \(\text{blood,speed}\) ，描述队列中的每个怪物。

输出格式

第一行两个整数,表示游戏结束时的回合数和游戏结束时基地的剩余血量。

第二行描述游戏的结果。若小B胜利，输出 Victory!，否则输出 Xiao B is SB!。

接下来 \(\text{q}\) 行,按照输入顺序描述每个怪物的状态:

若该怪物死亡，则输出 Died in round {死亡的回合数}。

若该怪物到达你的基地，则输出 Arrived your base in round {到达的回合数}。

若该怪物在游戏结束时还未生成或是还在地图中，则输出 The game has been over!。

样例 1

输入

5 5
S1###
001##
#0###
#0002
###0T
2
1 1 0
1 2 2
3
3 1
3 1
5 1

输出

10 10
Victory!
Died in round 3
Died in round 4
Died in round 10

样例 2

输入

输出

11 0
Xiao B is SB!
Arrived your base in round 2
Arrived your base in round 3
Arrived your base in round 4
Arrived your base in round 5
Arrived your base in round 6
Arrived your base in round 7
Arrived your base in round 8
Arrived your base in round 9
Arrived your base in round 10
Arrived your base in round 11

几个小时的成果：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }

    return x * f;
}
int a[15][15];
struct map_point {
    int x, y, fuck;
} point[105][101];
struct guai_now {
    int x, y;
} go[101];
int cnt[10], to[51];
bool vis[11][11];
int ddis(guai_now a, map_point b) { //a 怪 b 塔
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int dis(guai_now a, guai_now b) { //a 怪 b 怪
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int diss(map_point a, guai_now b, guai_now c) { //塔 目标怪 怪
    return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) * ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) *
            (c.x - a.x)); //叉积
}
int overstep;
bool over;
void search(int nowx, int nowy, int dep) {
    vis[nowx][nowy] = 1;
    go[dep].x = nowx;
    go[dep].y = nowy;

    if (!vis[nowx + 1][nowy] && a[nowx + 1][nowy] == 13)
        search(nowx + 1, nowy, dep + 1);

    if (!vis[nowx - 1][nowy] && a[nowx - 1][nowy] == 13)
        search(nowx - 1, nowy, dep + 1);

    if (!vis[nowx][nowy + 1] && a[nowx][nowy + 1] == 13)
        search(nowx, nowy + 1, dep + 1);

    if (!vis[nowx][nowy - 1] && a[nowx][nowy - 1] == 13)
        search(nowx, nowy - 1, dep + 1);

    if (!over && !vis[nowx + 1][nowy] && a[nowx + 1][nowy] == 11)
        over = 1, overstep = dep + 1;

    if (!over && !vis[nowx - 1][nowy] && a[nowx - 1][nowy] == 11)
        over = 1, overstep = dep + 1;

    if (!over && !vis[nowx][nowy + 1] && a[nowx][nowy + 1] == 11)
        over = 1, overstep = dep + 1;

    if (!over && !vis[nowx][nowy - 1] && a[nowx][nowy - 1] == 11)
        over = 1, overstep = dep + 1;
}
void make_map() {
    int n, m;
    string map;
    n = read();
    m = read();

    for (int i = 1; i <= n; i++) {
        cin >> map;

        for (int j = 0; j < map.size(); j++) {
            if (map[j] == 'S')
                a[i][j + 1] = 10, point[10][1].x = i, point[10][1].y = j + 1;
            else if (map[j] == 'T')
                a[i][j + 1] = 11, point[11][1].x = i, point[11][1].y = j + 1;
            else if (map[j] == '#')
                a[i][j + 1] = 12;
            else {
                a[i][j + 1] = map[j] - '0';

                if (a[i][j + 1] != 0) {
                    ++cnt[a[i][j + 1]];
                    point[a[i][j + 1]][cnt[a[i][j + 1]]].x = i;
                    point[a[i][j + 1]][cnt[a[i][j + 1]]].y = j + 1;
                } else
                    a[i][j + 1] = 13;
            }
        }
    }
}
struct ta_health {
    int damage, distance, type;
} ta[101];
void make_ta() {
    int n;
    n = read();

    for (int i = 1; i <= n; i++) {
        ta[i].damage = read();
        ta[i].distance = read();
        ta[i].type = read();
    }
}
struct guai_health {
    int blood, speed;
    bool js;
} guai[51];
int guaii;
void make_guai() {
    int n;
    n = read();
    guaii = n;

    for (int i = 1; i <= n; i++) {
        guai[i].blood = read();
        guai[i].speed = read();
    }
}
int guai_cnt;
void miao(int now) {
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= cnt[i]; j++) {
            if (guai[point[i][j].fuck].blood <= 0)
                point[i][j].fuck = 0;

            if (ddis(go[to[point[i][j].fuck]], point[i][j]) > ta[i].distance * ta[i].distance)
                point[i][j].fuck = 0;

            if (point[i][j].fuck != 0 && guai[point[i][j].fuck].blood > 0 &&
                    ddis(go[to[point[i][j].fuck]], point[i][j]) <= ta[i].distance * ta[i].distance)
                continue;//还是之前的目标

            for (int k = 1; k <= guai_cnt; k++) {
                if (guai[k].blood <= 0)
                    continue;//重新锁敌不考虑死去的

                if (ddis(go[to[k]], point[i][j]) > ta[i].distance * ta[i].distance)
                    continue;//没在攻击范围内

                if (point[i][j].fuck == 0) { //有在范围内的先锁上
                    point[i][j].fuck = k;
                    continue;
                }

                if (to[k] > to[point[i][j].fuck]) { //优先选择靠前的
                    point[i][j].fuck = k;
                    continue;
                }

                if (to[k] == to[point[i][j].fuck]) { //站位一样
                    if (guai[k].blood < guai[point[i][j].fuck].blood) { //优先选择血量少的
                        point[i][j].fuck = k;
                        continue;
                    }

                    if (guai[k].blood == guai[point[i][j].fuck].blood) {
                        if (k < point[i][j].fuck) { //出来的早的
                            point[i][j].fuck = k;
                            continue;
                        }
                    }
                }
            }
        }
    }
}
void attack(int now) {
    for (int i = 1; i <= 9; i++) {
        if (ta[i].type == 0) {
            for (int j = 1; j <= cnt[i]; j++) {
                guai[point[i][j].fuck].blood -= ta[i].damage;
            }
        }

        if (ta[i].type == 1) {
            for (int j = 1; j <= cnt[i]; j++) {
                if (point[i][j].fuck == 0)
                    continue;

                for (int k = 1; k <= guai_cnt; k++) {
                    if (dis(go[to[point[i][j].fuck]], go[to[k]]) <= 1 * 1) {
                        guai[k].blood -= ta[i].damage;
                    }
                }
            }
        }

        if (ta[i].type == 2) {
            for (int j = 1; j <= cnt[i]; j++) {
                if (point[i][j].fuck == 0)
                    continue;

                for (int k = 1; k <= guai_cnt; k++) {
                    if (diss(point[i][j], go[to[point[i][j].fuck]], go[to[k]]) <= ddis(go[to[point[i][j].fuck]], point[i][j])) {
                        guai[k].blood -= ta[i].damage;
                    }
                }
            }
        }

        if (ta[i].type == 3) {
            for (int j = 1; j <= cnt[i]; j++) {
                if (point[i][j].fuck == 0)
                    continue;

                guai[point[i][j].fuck].blood -= ta[i].damage;

                if (guai[point[i][j].fuck].js == 0) {
                    guai[point[i][j].fuck].js = 1;
                    guai[point[i][j].fuck].speed--;
                }
            }
        }
    }
}
int diey[1001];
void panduan(int now) {
    for (int i = 1; i <= guai_cnt; i++) {
        if (diey[i] == 0 && guai[i].blood <= 0) {
            diey[i] = now;
        }
    }
}
int arrive[101];
int T_blood = 10;
void yidong(int now) {
    for (int i = 1; i <= guai_cnt; i++) {
        to[i] += guai[i].speed;

        if (guai[i].blood > 0 && to[i] >= overstep) {
            T_blood--;
            guai[i].blood = -1;
            arrive[i] = now;
        }
    }

    if (T_blood <= 0) {
        cout << now << " " << T_blood << endl;
        cout << "Xiao B is SB!" << endl;

        for (int i = 1; i <= guaii; i++) {
            if (!arrive[i]) {
                if (diey[i])
                    cout << "Died in round " << diey[i] << endl;
                else
                    cout << "The game has been over!" << endl;
            } else {
                cout << "Arrived your base in round " << arrive[i] << endl;
            }
        }

        exit(0);
    }

    if (guai_cnt == guaii) {
        bool flagg = 0;

        for (int i = 1; i <= guai_cnt; i++) {
            if (guai[i].blood > 0) {
                flagg = 1;
                break;
            }
        }

        if (flagg == 0) {
            cout << now << " " << T_blood << endl;
            cout << "Victory!" << endl;

            for (int i = 1; i <= guai_cnt; i++) {
                if (!arrive[i]) {
                    cout << "Died in round " << diey[i] << endl;
                } else {

                    cout << "Arrived your base in round " << arrive[i] << endl;
                }
            }

            exit(0);
        }
    }
}
void game_begin(int now) {
    if (now <= guaii) {
        to[now] = 0;
        guai_cnt++;
    }

    miao(now);
    attack(now);
    panduan(now);
    yidong(now);
    game_begin(now + 1);

}
int main() {
    // freopen("earth.in","r",stdin);
    // freopen("earth.out","w",stdout);
    make_map();
    search(point[10][1].x, point[10][1].y, 0);
    make_ta();
    make_guai();
    game_begin(1);
    fclose(stdin);
    fclose(stdout);
    return 0;
}