荆轲刺秦王

题目

P6474

解析

显然，这是一道广搜
先考虑给每一个士兵能看到的点打标记，发现暴力打标记是$O(n^2{m}^2)$的，可以通过前缀和优化到$O(n^{2}m)$
打完标记，直接慢慢敲广搜即可
注意事项
个人提醒：本人曾经写过95分，后来发现是第18个数据跑了7秒，所以请各位把register拆出来，并吸氧等以卡常，写得优美一些

code:

#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define rr register int
using namespace std;
inline int min(int x,int y){
    return x<y?x:y;}
inline int max(int x,int y){
    return x>y?x:y;}
inline bool idigit(char x){
    return (x<'0'|x>'9')?0:1;}
inline int read()
{
    
	int num=0,f=1;
	char c=0;
	while(!idigit(c=getchar()))if(c=='S'||c=='T'||c=='.')break;
	if(!idigit(c))return (c=='S')?(-1):((c=='T')?(-2):0);
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num*f;
}
int n,m,c1,c2,dis,d[351][352][16][16],dx[8]={
    1,0,0,-1,1,1,-1,-1},dy[8]={
    0,1,-1,0,1,-1,-1,1},q[351][352],t,sx,sy,sa,sb,rx,ry,tx,ty,qwq,m1=998244353,m2=16,m3=16;
bool vis[351][352][16][16],lo[351][352];
inline void die(int x,int y,int z){
    for(int i=0;i<=z;++i)++q[max(x-i,1)][max(y-z+i,1)],--q[max(x-i,1)][min(y+z-i,m)+1],++q[min(x+i,n)][max(y-z+i,1)],--q[min(x+i,n)][min(y+z-i,m)+1];}
inline int check(int x,int y,int aa,int bb){
    if(1>x||n<x||1>y||m<y||lo[x][y]||vis[x][y][aa][bb])return 0;return (!q[x][y])?1:(aa==c1)?0:2;}
struct tr{
    int x,y,a,b;};
queue <tr> a;
int main()
{
    
	memset(d,0x3f,sizeof(d));
	n=read(),m=read(),c1=read(),c2=read(),dis=read();
	for(rr i=1;i<=n;++i)for(rr j=1;j<=m;++j)
	{
    
		t=read();
		if(t==-1)sx=i,sy=j;
		else if(t==-2)rx=i,ry=j;
		else if(t)die(i,j,t-1),lo[i][j]=1;
	}
	vis[sx][sy][0][0]=1,d[sx][sy][0][0]=0;
	for(rr i=1;i<=n;++i)for(rr j=1;j<=m;++j)q[i][j]+=q[i][j-1];
	a.push((tr){
    sx,sy,0,0});
	while(a.size())
	{
    
		sx=a.front().x,sy=a.front().y,sa=a.front().a,sb=a.front().b,a.pop();
		if(d[sx][sy][sa][sb]>m1)continue;
		if(sx==rx&&sy==ry)
		{
    
			if(d[sx][sy][sa][sb]<m1||d[sx][sy][sa][sb]==m1&&(sa+sb<m2+m3||sa+sb==m2+m3&&sa<m2))m1=d[sx][sy][sa][sb],m2=sa,m3=sb;
			continue;
		}
		for(rr i=0;i<=7;++i)
		{
    
			tx=sx+dx[i],ty=sy+dy[i];
			qwq=check(tx,ty,sa,sb);
			if(!qwq)continue;
			if(qwq==1){
    if(d[tx][ty][sa][sb]>d[sx][sy][sa][sb]+1)a.push((tr){
    tx,ty,sa,sb}),vis[tx][ty][sa][sb]=1,d[tx][ty][sa][sb]=d[sx][sy][sa][sb]+1;}
			else if(d[tx][ty][sa+1][sb]>d[sx][sy][sa][sb]+1)a.push((tr){
    tx,ty,sa+1,sb}),vis[tx][ty][sa+1][sb]=1,d[tx][ty][sa+1][sb]=d[sx][sy][sa][sb]+1;
		}
		if(sb==c2)continue;
		for(rr i=0;i<=3;++i)
		{
    
			tx=sx+dx[i]*dis,ty=sy+dy[i]*dis;
			qwq=check(tx,ty,sa,sb+1);
			if(!qwq)continue;
			if(qwq==1){
    if(d[tx][ty][sa][sb+1]>d[sx][sy][sa][sb]+1)a.push((tr){
    tx,ty,sa,sb+1}),vis[tx][ty][sa][sb+1]=1,d[tx][ty][sa][sb+1]=d[sx][sy][sa][sb]+1;}
			else if(d[tx][ty][sa+1][sb+1]>d[sx][sy][sa][sb]+1)a.push((tr){
    tx,ty,sa+1,sb+1}),vis[tx][ty][sa+1][sb+1]=1,d[tx][ty][sa+1][sb+1]=d[sx][sy][sa][sb]+1;
		}
	}
	if(m1==998244353)printf("-1");
	else printf("%d %d %d",m1,m2,m3);
	return 0;
}