Zizhou880 @ 2024-11-20 21:38:32
#include<bits/stdc++.h>
#include<bitset>
#define int long
#define INF 0x3f3f3f3f
using namespace std;
int x=0,y,z,r,c,k=1,ans=0,cnt=0,mans=INF,mx,my,lk,kkx,kky,kkxx,kkyy;
char a;
int b;
short dis[50][50][50][50];//骑士到终点的距离
bool sit[50][50];
bool king[50][50];
bool aim[50][50];//任意bfs终点
queue<int> qx;
queue<int> qy;
vector<int> vx;
vector<int> vy;//终点位置s
vector<int> kx;
vector<int> ky;//骑士位置
vector<int> kdis;
//int kdis;//骑士到王的距离
bitset<50> vis[50];
priority_queue<int,vector<int>,greater<int> > ex;//最少额外花费
priority_queue<int,vector<int>,greater<int> > fnl;//答案
void bfs(int x,int y)
{
qx.push(x);qy.push(y);
qx.push(-1);qy.push(-1);
vis[x][y]=1;
while(qx.front()!=-1||qx.back()!=-1)
{
if(sit[qx.front()][qy.front()]==1)
{
dis[x][y][qx.front()][qy.front()]=cnt;
ans+=cnt;
}
if(qx.front()==-1)
{
qx.push(-1);
qy.push(-1);
cnt++;
qx.pop();
qy.pop();
continue;
}
if(qx.front()-1>0)
{
if(qy.front()-2>0&&vis[qx.front()-1][qy.front()-2]!=true)
{
qx.push(qx.front()-1);
qy.push(qy.front()-2);
vis[qx.front()-1][qy.front()-2]=true;
}
if(qy.front()+2<=r&&vis[qx.front()-1][qy.front()+2]!=true)
{
qx.push(qx.front()-1);
qy.push(qy.front()+2);
vis[qx.front()-1][qy.front()+2]=true;
}
}//x-1
if(qx.front()-2>0)
{
if(qy.front()-1>0&&vis[qx.front()-2][qy.front()-1]!=true)
{
qx.push(qx.front()-2);
qy.push(qy.front()-1);
vis[qx.front()-2][qy.front()-1]=true;
}
if(qy.front()+1<=r&&vis[qx.front()-2][qy.front()+1]!=true)
{
qx.push(qx.front()-2);
qy.push(qy.front()+1);
vis[qx.front()-2][qy.front()+1]=true;
}
}//x-2
if(qx.front()+1<=c)
{
if(qy.front()-2>0&&vis[qx.front()+1][qy.front()-2]!=true)
{
qx.push(qx.front()+1);
qy.push(qy.front()-2);
vis[qx.front()+1][qy.front()-2]=true;
}
if(qy.front()+2<=r&&vis[qx.front()+1][qy.front()+2]!=true)
{
qx.push(qx.front()+1);
qy.push(qy.front()+2);
vis[qx.front()+1][qy.front()+2]=true;
}
}//x+1
if(qx.front()+2<=c)
{
if(qy.front()-1>0&&vis[qx.front()+2][qy.front()-1]!=true)
{
qx.push(qx.front()+2);
qy.push(qy.front()-1);
vis[qx.front()+2][qy.front()-1]=true;
}
if(qy.front()+1<=r&&vis[qx.front()+2][qy.front()+1]!=true)
{
qx.push(qx.front()+2);
qy.push(qy.front()+1);
vis[qx.front()+2][qy.front()+1]=true;
}
}//x+2
qx.pop();qy.pop();
}
}
int bfs_k(int x,int y,int p,int q)//(x,y) -> (p,q)
{
aim[p][q]=1;
ans=0;cnt=0;
qx.push(x);qy.push(y);
qx.push(-1);qy.push(-1);
vis[x][y]=1;
while(qx.front()!=-1||qx.back()!=-1)
{
if(aim[qx.front()][qy.front()]==1)
{
ans=cnt;
break;
}
if(qx.front()==-1)
{
qx.push(-1);
qy.push(-1);
cnt++;
qx.pop();
qy.pop();
continue;
}
if(qx.front()-1>0)
{
if(qy.front()-2>0&&vis[qx.front()-1][qy.front()-2]!=true)
{
qx.push(qx.front()-1);
qy.push(qy.front()-2);
vis[qx.front()-1][qy.front()-2]=true;
}
if(qy.front()+2<=r&&vis[qx.front()-1][qy.front()+2]!=true)
{
qx.push(qx.front()-1);
qy.push(qy.front()+2);
vis[qx.front()-1][qy.front()+2]=true;
}
}//x-1
if(qx.front()-2>0)
{
if(qy.front()-1>0&&vis[qx.front()-2][qy.front()-1]!=true)
{
qx.push(qx.front()-2);
qy.push(qy.front()-1);
vis[qx.front()-2][qy.front()-1]=true;
}
if(qy.front()+1<=r&&vis[qx.front()-2][qy.front()+1]!=true)
{
qx.push(qx.front()-2);
qy.push(qy.front()+1);
vis[qx.front()-2][qy.front()+1]=true;
}
}//x-2
if(qx.front()+1<=c)
{
if(qy.front()-2>0&&vis[qx.front()+1][qy.front()-2]!=true)
{
qx.push(qx.front()+1);
qy.push(qy.front()-2);
vis[qx.front()+1][qy.front()-2]=true;
}
if(qy.front()+2<=r&&vis[qx.front()+1][qy.front()+2]!=true)
{
qx.push(qx.front()+1);
qy.push(qy.front()+2);
vis[qx.front()+1][qy.front()+2]=true;
}
}//x+1
if(qx.front()+2<=c)
{
if(qy.front()-1>0&&vis[qx.front()+2][qy.front()-1]!=true)
{
qx.push(qx.front()+2);
qy.push(qy.front()-1);
vis[qx.front()+2][qy.front()-1]=true;
}
if(qy.front()+1<=r&&vis[qx.front()+2][qy.front()+1]!=true)
{
qx.push(qx.front()+2);
qy.push(qy.front()+1);
vis[qx.front()+2][qy.front()+1]=true;
}
}//x+2
qx.pop();qy.pop();
}
aim[p][q]=0;
while(!qx.empty()) qx.pop();
while(!qy.empty()) qy.pop();
for(int i=1;i<=c;i++)
vis[i].reset();
return ans;
}
signed main()
{
cin>>r>>c;
while(cin>>a>>b)
{
if(z==0)
{
z=1;
king[b][a-'A'+1]=1;
kkx=b;kky=a-'A'+1;
}
else
{
sit[b][a-'A'+1]=1;
kx.push_back(b);
ky.push_back(a-'A'+1);
}
}
if(kx.empty())
{
cout<<0<<endl;
return 0;
}
for(int i=1;i<=c;i++)
for(int j=1;j<=r;j++)
{
bfs(i,j);
if(mans==ans)
{
vx.push_back(i);
vy.push_back(j);
}
if(mans>ans)
{
mans=ans;
mx=i;
my=j;
vx.clear();
vy.clear();
vx.push_back(i);
vy.push_back(j);
}
qx.pop();qy.pop();
cnt=0;ans=0;
for(int i=1;i<=c;i++)
for(int j=1;j<=r;j++)
vis[i][j]=0;
}
kkxx=kkx;kkyy=kky;
for(int m=-5;m<=5;m++)
for(int n=-5;n<=5;n++)
{
kkx=kkxx+m;
kky=kkyy+n;
if(kkx<1||kky<1)
continue;
if(kkx>r||kky>c)
continue;
for(int i=0;i<=kx.size()-1;i++)
{
kdis.push_back(bfs_k(kx[i],ky[i],kkx,kky));
}
for(int i=0;i<=vx.size()-1;i++)
{
lk=bfs_k(kkx,kky,vx[i],vy[i]);
for(int j=0;j<=kx.size()-1;j++)
{
ex.push(kdis[j]+lk-dis[vx[i]][vy[i]][kx[j]][ky[j]]+max(abs(m),abs(n)));
}
}
kdis.clear();
}
cout<<mans+ex.top()<<endl;
return 0;
}
https://www.luogu.com.cn/record/187523714
谢谢！