题目描述

时隔数年，刺客荆轲再次来到咸阳宫，试图刺杀嬴政。

咸阳宫的地图可以描述为一个 n 行 m 列的矩形。

在这里，我们规定每一行中从左到右为 x 轴正方向，每一列中从下到上为 y 轴正方向，左下角的点坐标为 (1,1)。

矩形中的点可以分为 4 种：

起点，也就是荆轲的所在点，在地图中用字符 S 代表。
终点，也就是嬴政的所在点，在地图中用字符 T 代表。
卫兵，在地图中用一个正整数 ai,j 代表。在这里，一个卫兵 (i,j) 可以观察到与他曼哈顿距离小于 ai,j 的点。也就是卫兵 (i,j) 可以观察到所有满足 |x−i|+|y−j|<ai,j 的点 (x,y)。
空地，在地图中用字符 . 代表。
荆轲的正常移动方式为每秒向八连通的任意方向前进一格。

如下图，中间的点为荆轲当前所在点，每一秒，他可以走向其余的八个点。

ss.png

需要注意的是，正常移动时，荆轲不能踏进任何一个有卫兵或者卫兵能观察到的格子。当然，他也不能走出咸阳宫，也就是说，无论何时，荆轲的坐标 (x,y) 都必须满足 1≤x≤m 且 1≤y≤n。

荆轲还有两种技能：隐身和瞬移。

隐身：下一秒荆轲进入隐身状态，卫兵观察不到荆轲，荆轲可以进入卫兵的观察范围内，但仍然不能进入卫兵所在的格子。注意这个状态只能维持一秒。
瞬移：荆轲下一秒移动的距离改为 d，但这时只能向上下左右四个方向移动。即可以移动到
(x+d,y)，(x−d,y)，(x,y+d)，(x,y−d)。
在本题中，两种技能可以同时使用，而且不考虑冷却时间，即一次用完可以立即用下一次，两种技能都分别有使用次数限制，你也可以不用完所有次数。

现在给出咸阳城的地图，请计算荆轲到达秦王所在点所需的最短时间。

此外，在所用时间相同情况下，荆轲希望使用的两种技能总次数尽可能少；在所用时间与技能次数相同情况下，荆轲希望使用的隐身次数尽可能少。

本题暂时采用 AcWing 自行生成数据。

输入格式

第一行五个整数 n, m, c1, c2, d，代表地图的大小为 n×m，隐身的使用限制次数为 c1，瞬移的使用限制次数为 c2 和一次瞬移的距离为 d。

接下来 n 行，每行 m 个元素。每个元素为字符 S、T、. 或者一个正整数 ai,j，代表一个格点，具体含义详见题目描述。

输出格式

若荆轲无法到达秦王所在点，则输出一行一个 −1。

否则输出一行三个整数 t, u1, u2，依次代表所需的最短时间，隐身的使用次数与瞬移的使用次数。

数据范围

对于测试点 1∼6：n, m≤10，c1=c2=0，保证所需的最短时间不超过 5 或者无解。

对于测试点 7∼10：n, m≤20，c1=c2=0，保证 T 的位置不在任何一个卫兵的观察范围之中。

对于测试点 11∼12：n, m≤20，c1=0
对于测试点 13∼14：n, m≤20，c1, c2≤5。

对于测试点 15∼16：卫兵个数不超过 350。

对于所有测试点：2≤n, m≤350，1≤ai,j≤350，0≤c1, c2≤15，1≤d≤350。

保证 S 的位置不在任何卫兵的观察范围中。。

输出格式

输入样例1：
5 4 0 0 5
. 1 T 1
. . . 2
. 1 . .
S . . .
1 . . .
输出样例1：
3 0 0
样例1解释
起点为 (1,2)，荆轲可以依次走到 (1,3), (2,4), (3,5) 到达终点。

输入样例2：
8 6 2 3 3
. S . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
2 . 2 . 2 .
. . 1 . T .
3 . 1 . . 3
输出样例2：
3 1 3
样例2解释
起点为 (2,8)，荆轲可以依次走到 (2,5), (2,2), (5,2)，需要注意的是，即使最后一步到达终点，但因为终点在卫兵的观察范围之内，所以仍然需要隐身进入。

输入样例3：
8 6 5 5 2
. S . . . .
. . . . . .
. . . . . .
1 1 3 2 . 1
2 3 2 2 1 3
3 2 4 1 4 3
2 6 1 5 T 2
8 1 6 3 2 10
输出样例3：
-1

算法1

(广搜) $O(n^2)$

呵呵呵

时间复杂度

参考文献

C++ 代码

#include <queue>
#include <cstdio>
#include <cstring>
#define cint const int
#define rint register int

const int Inf=0x3f3f3f3f,Dx[]={-1,-1,-1,0,1,1,1,0},Dy[]={-1,0,1,1,1,0,-1,-1};
int n,m,c1,c2,D,Sx,Sy,Tx,Ty,Md=Inf;
int s[355][355],ss[355][355],Dis[50000005],q[35000005],qh,qt;
//s[i][j]表示是否被卫兵观察，ss[i][j]表示是否有卫兵，Dis[i]表示最短时间，q[i]为BFS队列
char r[15];

struct Cr{int x,y,a;inline bool operator<(const Cr& o)const{return a<o.a;}};
#define H(a,b,c,d) (((a)<<17)|((b)<<8)|((c)<<4)|(d))
//状态压缩函数

int Get()//读入一个点
{
    scanf("%s",r);
    if(*r=='.')return 0;
    if(*r=='S')return -1;
    if(*r=='T')return -2;
    int a=0,l=strlen(r);
    for(int i=0;i<l;++i)a=a*10+(r[i]^48);
    return a;
}

void PCover()
//预处理，用的是优先队列的版本
{
    std::priority_queue<Cr> q;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(s[i][j]>0)
                q.push((Cr){i,j,s[i][j]});
    for(int x,y,a;!q.empty();)
    {
        x=q.top().x,y=q.top().y,a=q.top().a,q.pop();
        if(s[x][y]>a)continue;
        for(int i=1,nx,ny;i<8;i+=2)
        {
            nx=x+Dx[i],ny=y+Dy[i];
            if(nx<1||nx>n||ny<1||ny>m||s[nx][ny]>=a-1)continue;
            q.push((Cr){nx,ny,s[nx][ny]=a-1});
        }
    }
}

void BFS()
{
    memset(Dis,0x3f,sizeof Dis),Dis[q[0]=H(Sx,Sy,0,0)]=0;
    for(rint x,y,u1,u2,d,Nv,Wv;qh<=qt;)
    {
        Nv=q[qh++],x=Nv>>17,y=Nv>>8&0x1ff,u1=Nv>>4&0xf,u2=Nv&0xf,d=Dis[Nv];
        //取出队首并且解压缩
        if(d>=Md||ss[x][y]>0)continue;
        if(x==Tx&&y==Ty)Md=d;//最优性剪枝
        for(rint i=0,nx,ny,j;i<8;++i)
        {
            nx=x+Dx[i],ny=y+Dy[i];
            if(nx<1||nx>n||ny<1||ny>m)continue;
            j=s[nx][ny]>0;//是否需要隐身
            if(u1+j<=c1&&Dis[Wv=H(nx,ny,u1+j,u2)]>d+1)Dis[q[++qt]=Wv]=d+1;
            if(i&1)//瞬移技能
            {
                nx=x+Dx[i]*D,ny=y+Dy[i]*D;
                if(nx<1||nx>n||ny<1||ny>m)continue;
                j=s[nx][ny]>0;
                if(u1+j<=c1&&u2+1<=c2&&Dis[Wv=H(nx,ny,u1+j,u2+1)]>d+1)Dis[q[++qt]=Wv]=d+1;
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("bandit.out","w",stdout);
    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)
            if((ss[i][j]=s[i][j]=Get())==-1)Sx=i,Sy=j;
            else if(s[i][j]==-2)Tx=i,Ty=j;
    PCover(),BFS();
    rint A1=Inf,A2=Inf,A3=Inf,d;
    for(rint i=0;i<=c1;++i)
        for(rint j=0;j<=c2;++j)
            if((d=Dis[H(Tx,Ty,i,j)])<A1||(d==A1&&i+j<A2+A3)||(d==A1&&i+j==A2+A3&&i<A2))
                A1=d,A2=i,A3=j;
    if(A1==Inf)puts("-1");
    else printf("%d %d %d\n",A1,A2,A3);
    return 0;
}

`