荆轲将会臭名昭著
首先 $15$ 做法很简单，那就是直接 `cout<<-1`
考虑用 BFS 来解思路很简单，但是怎么求每个士兵的控制范围呢？
直接暴力时间复杂度是 $O(nma^2)$ 当然过不了一定会TLE。
所以，只需要差分+前缀和即可。
说起来简单，实现起来也简单。
然后，单打广搜大家应该都会了，可是出题人的恶魔 $18$ 点可以让你的代码慢到爆炸！
怎么剪枝呢？也很简单。
只需将当前步数大于之前已走到终点点数的点删去就可以了。
就这么简单，但我还是打了5个多小时。
然后...
正片开始！
起初，神创造了差分。标记数组是空虚混沌的，渊面黑暗，神的灵运行在差分的左右端点上。
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%s",s);
if(s[0]=='S')
{
sx=i;
sy=j;
}
else if(s[0]=='T')
{
tx=i;
ty=j;
}
else if(s[0]!='.')
{
pers[i][j]=true;
int len=strlen(s),num=0;
for(int k=0;k<len;k++)
{
num=num*10+s[k]-'0';
}
for(int t=max(1,i-num+1);t<=min(n,i+num-1);t++)
{
int l=max(1,j-num+1+abs(i-t));
int r=min(m,j+num-1-abs(i-t));
cov[t][l]++;
cov[t][r+1]--;
}
}
}
}
神说差分数组要有值，与是差分数组变有了值。
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cov[i][j]+=cov[i][j-1];
}
}
神看这值是对的，与是就把差分数组的预处理分为两段。有晚上，有早晨，是第一日。
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%s",s);
if(s[0]=='S')
{
sx=i;
sy=j;
}
else if(s[0]=='T')
{
tx=i;
ty=j;
}
else if(s[0]!='.')
{
pers[i][j]=true;
int len=strlen(s),num=0;
for(int k=0;k<len;k++)
{
num=num*10+s[k]-'0';
}
for(int t=max(1,i-num+1);t<=min(n,i+num-1);t++)
{
int l=max(1,j-num+1+abs(i-t));
int r=min(m,j+num-1-abs(i-t));
cov[t][l]++;
cov[t][r+1]--;
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cov[i][j]+=cov[i][j-1];
}
}
神说数组之间要有 BFS 将其应用，神就造出了 BFS，将 BFS 以外叫做#？，BFS 以内叫做？#，这样就成了，神称 BFS 为函数，有晚上，有早晨，是第二日。
void bfs()
{
queue<node>q;
q.push(#??#);
}
...
OK，95分大成！
满分做法啊...
[好好研究](https://www.luogu.com.cn/discuss/281304)[.](https://www.luogu.com.cn/paste/fpmecy7i)
当然，上面说了，自己改吧！
我把95分的贴出来，100的就不贴了。
const int N=360,M=20;
int n,m,c1,c2,dist;
int sx,sy,tx,ty;
int cov[N][N];
bool pers[N][N];
struct node
{
int x,y,u1,u2;
node(int v1,int v2,int v3,int v4) :
x(v1),y(v2),u1(v3),u2(v4) {}
};
int d[N][N][M][M];
int vis[N][N][M][M];
const int dx[8]={-1,0,1,0,-1,1,1,-1},dy[8]={0,1,0,-1,1,1,-1,-1};
bool cmp(int x,int y)
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
void bfs()
{
queue<node>q;
d[sx][sy][0][0]=0;
vis[sx][sy][0][0]=true;
q.push((node){sx,sy,0,0});
while(!q.empty())
{
node u=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int nx=u.x+dx[i];
int ny=u.y+dy[i];
if(cmp(nx,ny)&&!pers[nx][ny])
{
//cout<<nx<<" "<<ny<<" "<<u.x<<" "<<u.y<<" ";
if(cov[nx][ny])
{
if(u.u1+1<=c1&&!vis[nx][ny][u.u1+1][u.u2])
{
d[nx][ny][u.u1+1][u.u2]=d[u.x][u.y][u.u1][u.u2]+1;
vis[nx][ny][u.u1+1][u.u2]=true;
//cout<<nx<<" "<<ny<<"\n";
q.push((node){nx,ny,u.u1+1,u.u2});
}
}
else
{
if(!vis[nx][ny][u.u1][u.u2])
{
d[nx][ny][u.u1][u.u2]=d[u.x][u.y][u.u1][u.u2]+1;
vis[nx][ny][u.u1][u.u2]=true;
//cout<<nx<<" "<<ny<<"\n";
q.push((node){nx,ny,u.u1,u.u2});
}
}
}
}
if(u.u2+1<=c2)
{
for(int i=0;i<4;i++)
{
int nx=u.x+dx[i]*dist,ny=u.y+dy[i]*dist;
if(cmp(nx,ny)&&!pers[nx][ny])
{
if(cov[nx][ny])
{
if(u.u1+1<=c1&&!vis[nx][ny][u.u1+1][u.u2+1])
{
d[nx][ny][u.u1+1][u.u2+1]=d[u.x][u.y][u.u1][u.u2]+1;
vis[nx][ny][u.u1+1][u.u2+1]=true;
//cout<<nx<<" "<<ny<<"\n";
q.push((node){nx,ny,u.u1+1,u.u2+1});
}
}
else
{
if(!vis[nx][ny][u.u1][u.u2+1])
{
d[nx][ny][u.u1][u.u2+1]=d[u.x][u.y][u.u1][u.u2]+1;
vis[nx][ny][u.u1][u.u2+1]=true;
//cout<<nx<<" "<<ny<<"\n";
q.push((node){nx,ny,u.u1,u.u2+1});
}
}
}
}
}
}
return ;
}
int main()
{
cin>>n>>m>>c1>>c2>>dist;
char s[4];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%s",s);
if(s[0]=='S')
{
sx=i;
sy=j;
}
else if(s[0]=='T')
{
tx=i;
ty=j;
}
else if(s[0]!='.')
{
pers[i][j]=true;
int len=strlen(s),num=0;
for(int k=0;k<len;k++)
{
num=num*10+s[k]-'0';
}
for(int t=max(1,i-num+1);t<=min(n,i+num-1);t++)
{
int l=max(1,j-num+1+abs(i-t));
int r=min(m,j+num-1-abs(i-t));
//cout<<l<<" "<<r<<"\n";
cov[t][l]++;
cov[t][r+1]--;
}
}
}
}
//cout<<"qidian "<<sx<<" "<<sy<<" zhongdian "<<tx<<" "<<ty<<"\n";
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cov[i][j]+=cov[i][j-1];
}
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<cov[i][j]<<" ";
}
cout<<"\n";
}*/
bfs();
int t=n*m,u1,u2;
for(int i=0;i<=max(c1,c2);i++)
{
for(int j=0;j<=max(c1,c2);j++)
{
if(vis[tx][ty][j][i]&&d[tx][ty][j][i]<t)
{
t=d[tx][ty][j][i];
u1=j;
u2=i;
}
}
}
if(t==n*m)
{
cout<<-1;
}
else
{
cout<<t<<" "<<u1<<" "<<u2;
}
return 0;
}
标签：node,sy,sx,int,题解,差分,BFS,Online,P6474 From： https://www.cnblogs.com/-Acheron-/p/18607288