题意

荆轲刺秦王

在方格地图内两点之间寻找最优路线(8宫格+技能)

优先选择时间最少的路线,其次选择总技能最少的,再选择隐身最少的,最后是瞬移最少的

注意,瞬移是只有4宫格的方向,普通移动是8宫格的

思路

通过方向数组记录位移偏差,不然每个方向都写就很难调代码了

这里可以只用一个方向数组,前4个是4宫格的,后四个是8宫格的

代码

#include<bits/stdc++.h>
#define pii pair<int,int>//位置
#define N 355
#define INF 0x3f3f3f3f
using namespace std;
int n,m,c1,c2,d;
int g[N][N];
int cf[N][N];
int xl[8]={0,0,1,-1,1,-1,1,-1};
int yl[8]={1,-1,0,0,1,-1,-1,1};
pii s,t;
bool check_e(int i,int j)//判断是否越界
{
	return i<1 || j<1 || i>n || j>m;
}
void fun(int x,int y,int d)//通过差分标记士兵的观察范围
{
	for(int i=0;i<=d;i++)//每一行
	{
		cf[max(1,x-i)][max(1,y-(d-i))]++;//左上
		cf[max(1,x-i)][min(y+(d-i),m)+1]--;//右上
		cf[min(x+i,n)][max(1,y-(d-i))]++;//左下
		cf[min(x+i,n)][min(y+(d-i),m)+1]--;//右下
	}
}
struct node
{
	pii p;//位置
	int st,c1,c2;//时间,剩下隐身的次数,剩下瞬移的次数
	bool operator < (const node nxt)const//比较哪个更优秀
	{
		if(st<nxt.st)
			return 1;
		else if(st==nxt.st)//时间
		{
			if(c1+c2>nxt.c1+nxt.c2)//总技能,剩下的技能越多的越好!!!
				return 1;
			else if(c1+c2==nxt.c1+nxt.c2)
			{
				if(c1>nxt.c1)//隐身,剩下的技能越多的越好!!!
					return 1;
				else if(c1==nxt.c1)
				{
					if(c2>nxt.c2)//瞬移,剩下的技能越多的越好!!!
						return 1;
				}
			}
		}
		return 0;
	}
};
queue<node>q;
bool vis[N][N][20][20];//需要4种状态记录
node bfs()
{
	q.push({s,0,c1,c2});//这里记录的是剩下的次数!!!不要搞错了
	node b={s,INF,c1,c2};//初始化
	while(!q.empty())
	{
		node e=q.front();q.pop();
		int x=e.p.first,y=e.p.second;
		if(e.st>b.st)continue;//择优剪枝
		if(vis[x][y][e.c1][e.c2])continue;
		vis[x][y][e.c1][e.c2]=1;
		if(pii{x,y}==t)
		{
			if(e<b)b=e;//是否更优秀
			continue;
		}
		for(int i=0;i<8;i++)//没有使用瞬移,8宫格
		{
			int xs=x+xl[i],ys=y+yl[i];
			if(check_e(xs,ys))continue;
			if(g[xs][ys]==2)continue;//这里是士兵,注意,不是观察范围,隐身也走不了
			if(!g[xs][ys])//不使用隐身
				q.push({{xs,ys},e.st+1,e.c1,e.c2});
			else if(e.c1)//使用隐身
				q.push({{xs,ys},e.st+1,e.c1-1,e.c2});//是减次数!!!
		}
		if(e.c2)//使用瞬移
		{
			for(int i=0;i<4;i++)//4宫格
			{
				int xs=x+d*xl[i],ys=y+d*yl[i];//记得有长度,需要 *d
				if(check_e(xs,ys))continue;
				if(g[xs][ys]==2)continue;//这里是士兵,注意,不是观察范围,隐身也走不了
				if(!g[xs][ys])//不使用隐身
					q.push({{xs,ys},e.st+1,e.c1,e.c2-1});//是减次数!!!
				else if(e.c1)//使用隐身
					q.push({{xs,ys},e.st+1,e.c1-1,e.c2-1});//是减次数!!!
			}
		}
	}
	return b;
}
int main()
{
	cin>>n>>m>>c1>>c2>>d;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			string o;cin>>o;//选择string进行输入
			if(o==".")continue;
			else if(o=="S")s={i,j};
			else if(o=="T")t={i,j};
			else fun(i,j,stoi(o)-1),g[i][j]=2;//士兵,记得fun的距离要减1
		}
	}
	for(int i=1;i<=n;i++)//通过差分数组求出原来的观察范围
	{
		int sum=0;
		for(int j=1;j<=m;j++)
		{
			sum+=cf[i][j];
			if(sum>0 && !g[i][j])//不要把士兵位置给标记了,会出错的
				g[i][j]=1;//观察范围是1,士兵是2
		}
	}
	node f=bfs();
	if(f.st!=INF)cout<<f.st<<" "<<c1-f.c1<<" "<<c2-f.c2;//我记录的是剩下的次数,所以需要用总次数减去
	else cout<<-1;
	return 0;
}