题面

题目大意

给定一张$n*m$的地图，包含有一个起点及一个终点，询问从起点到终点的最优路线。

其中人物的运动方法有两种，第一可以用正常的走法，可以向八个方向移动一格；第二可以用瞬移，我们使用一次瞬移技能就可以向四个方向移动$d$格。

分析阻挡人物运动的因素，第一就是人物不能超出地图边界（如果你的瞬移会导致你的坐标超出边界，这一次瞬移并不会进行而不是会瞬移到墙边）；第二就是落地时不能站在守卫的头上（但是我们可以用瞬移从守卫头上飞过去）；第三就是如果你落地时所在方块处在守卫的视野中（不需要考虑多少守卫的视野中），你需要立即使用一次隐身技能。

分析

读完题目我们很自然就会想到BFS，或者是带有priority_queue的Dijkstra，在这方面上的处理并不困难，每一次只要对当前状态进行扩展（即人物移动）即可。

但是我们同样遇到了一些难题。

第一，士兵的视野范围处理。

由于按照题目描述，士兵的视野范围看的是曼哈顿距离，所以他的视野范围画出来大概是这样的（视野为4）

   *
  ***
 *****
***4***
 *****
  ***
   *

小学时打了无数次的绘制图形题终于派上用场了

我这里使用的是差分方法，对于每一行在开头处$+1$，结尾处$-1$，最后$O(n^2)$前缀和处理，直接访问数组就可以得知当前坐标是否在士兵视野中。

当然，如果暴力直接在数组上扫出整个图形应该也不会超时（没有试过）。

第二，输入

输入的$n*m$的矩阵，跟平常不同。这个矩阵中又有数字又有字符的，应该如何处理。

看到有人用cin来解决，可能会方便一点，我这里采用更快的getchar写法。对于字符，只需正常getchar，对于数字么，用高精度输入的方法处理就可以了。（代码略微繁琐）

代码

我使用的是Dijkstra，其中$visit[i][j]$存放的是在坐标为$(i,j)$时所剩技能最优的情况。因为我们用的是priority_queue，所以显然先出队的一定是更优的情况。如果此时堆顶状态比$visit[i][j]$更差或相同，而显然这个$visit[i][j]$在达到时用时比现在更少，显然当前状态一定劣于那时的状态，直接continue。

而且由于使用的priority_queue会使先出队的更优，所以在搜到答案时直接输出即可，因为当前状态一定是所有达到终点的状态中最优的。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> cmptype; //visit数组所保存的类型

struct type
{
    int x, y, st1, st2, t;
    inline bool operator>(type b) const //优先队列要用
    {
        return (t > b.t || (t == b.t && (st1 + st2) > (b.st1 + b.st2)) || (t == b.t && (st1 + st2) == (b.st1 + b.st2) && st1 > b.st1));
    }
};

//方向数组
const int wayx[4] = {0, 0, 1, -1}, wayy[4] = {1, -1, 0, 0};
const int walkx[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, walky[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

char room[355][355], tree[355][355];                    //地图和守卫视线标记
int startx, starty, endx, endy;                         //起点和终点
int n, m, c1, c2, d;                                    //输入的五项
cmptype visit[355][355];                                //visit数组
priority_queue<type, vector<type>, greater<type> > que; //优先队列

int main()
{
    scanf("%d%d%d%d%d", &n, &m, &c1, &c2, &d);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            room[i][j] = getchar();
            while (room[i][j] != 'S' && room[i][j] != 'T' && room[i][j] != '.' && (room[i][j] < '1' || room[i][j] > '9'))
                room[i][j] = getchar(); //getchar读法
            if (room[i][j] == 'S')      //起点
            {
                startx = i;
                starty = j;
                room[i][j] = '.';
            }
            if (room[i][j] == 'T') //终点
            {
                endx = i;
                endy = j;
                room[i][j] = '.';
            }
            if (room[i][j] >= '1' && room[i][j] <= '9')
            { //高精输入
                int t = room[i][j] - '0';
                room[i][j] = '#';
                char c = getchar();
                while (c >= '0' && c <= '9')
                {
                    t = t * 10 + c - '0';
                    c = getchar();
                }
                for (int x = max(1, i - t + 1); x <= min(n, i + t - 1); x++)
                { //视野的标记（差分）
                    tree[x][max(1, j - t + 1 + abs(x - i))]++;
                    tree[x][min(m + 1, j + t - abs(x - i))]--;
                }
            }
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            tree[i][j] += tree[i][j - 1]; //对差分数组进行前缀和，使其正常
    memset(visit, 0x7f, sizeof(visit));
    que.push((type){startx, starty, 0, 0, 0}); //初始状态
    while (!que.empty())
    {
        type cac = que.top();
        que.pop();
        if (cac.st1 > c1 || cac.st2 > c2) //技能使用数量超过限制
            continue;
        if (cac.x == endx && cac.y == endy) //如果到达了终点
        {                                   //由于是优先队列，可以直接结束
            printf("%d %d %d\n", cac.t, cac.st1, cac.st2);
            return 0;
        }
        if (visit[cac.x][cac.y] <= (cmptype){cac.st1 + cac.st2, cac.st1}) //如果比上次访问到这里是方案更差，直接退出
            continue;
        visit[cac.x][cac.y] = (cmptype){cac.st1 + cac.st2, cac.st1};
        for (int i = 0; i < 8; i++)
        { //向八个方向运动一格
            int x = cac.x + walkx[i], y = cac.y + walky[i];
            if (x < 1 || x > n || y < 1 || y > m)
                continue;
            if (room[x][y] != '.')
                continue;
            bool inarea = tree[x][y] > 0;
            que.push((type){x, y, cac.st1 + inarea, cac.st2, cac.t + 1});
        }
        for (int i = 0; i < 4; i++)
        { //向四个方向瞬移d格
            int x = cac.x + wayx[i] * d, y = cac.y + wayy[i] * d;
            if (x < 1 || x > n || y < 1 || y > m)
                continue;
            if (room[x][y] != '.')
                continue;
            bool inarea = tree[x][y] > 0;
            que.push((type){x, y, cac.st1 + inarea, cac.st2 + 1, cac.t + 1});
        }
    }
    puts("-1"); //没有路径
    return 0;
}