恶心的题啊 。。
先枚举哪个点是所有人集合的点 再枚举所有骑士遇见国王的点 如果全部枚举出来会大大的TLE 经大牛验证 只需要枚举国王周围的点就可以了+-2 之内
然后各种繁琐 各种错误 骑士有可能不带着国王一块走 也可能在他周围选个点带着走 先预处理出来每个骑士到国王周围的最短距离 然后再按上面的枚举就可以了
考虑的不全面 。。错了好多个样例 样例2,6,19,20 都模拟了一遍。。还好错在小数据上 可以手算模拟一下 就知道哪错了 变量名都被我用穷了。。
/*
ID: shangca2
LANG: C++
TASK: camelot
*/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f
using namespace std;
int vis[][],dis[][] = {{,},{,-},{,},{,-},{-,-},{-,},{-,},{-,-}};
typedef struct node
{
int x,y,num;
}st;
st qq[];
int o[][][][],x[],y[],n,m,ans,xx,yy,f[][],g;
int ff[][],di,s;
int judge(int x,int y)
{
if(x<=||y<=||x>n||y>m)
return ;
return ;
}
int bfs(int xi,int yi,int e1,int e2,int flag)
{
queue<st>q;
s=;int ss=;
memset(vis,,sizeof(vis));
memset(ff,,sizeof(ff));
int i;
st tt,te;
tt.x = xi;
tt.y = yi;
tt.num = ;
vis[xi][yi] = ;
q.push(tt);
int fff = ;
while(!q.empty())
{
tt = q.front();
q.pop();
if(flag&&tt.x==e1&&tt.y==e2)
{
fff = ;
return tt.num;
}
o[xi][yi][tt.x][tt.y] = tt.num;
o[tt.x][tt.y][xi][yi] = tt.num;
if(f[tt.x][tt.y])
ss+=tt.num;
if(ss>ans)
return -;
for(i = ;i < ; i++)
{
int tx = tt.x+dis[i][];
int ty = tt.y+dis[i][];
if(judge(tx,ty)&&!vis[tx][ty])
{
te.x = tx;
te.y = ty;
te.num = tt.num+;
vis[tx][ty] = ;
q.push(te);
}
}
}
if(flag&&!fff)
return INF;
for(i = ; i <= g ;i++)
s+=o[xi][yi][x[i]][y[i]];
return s;
}
int main()
{
freopen("camelot.in","r",stdin);
freopen("camelot.out","w",stdout);
int i,j,k,e,ee;
for(i = ;i <= ; i++)
for(j = ;j <= ; j++)
for(e = ;e <= ; e++)
for(ee = ;ee <= ; ee++)
o[i][j][e][ee] = INF;
char c;
ans = INF;
cin>>n>>m;
cin>>c>>xx;
yy = c-'A'+;
while(cin>>c>>k)
{
int yg = c-'A'+;
int xg = k;
g++;
x[g] = xg;
y[g] = yg;
f[xg][yg] = ;
}
int dd[][] = {,,,,,-,,,-,,,,,-,-,,-,-,,,,,,,,-,,-,
-,,-,,-,,-,-,-,-,,,,,-,,,-,,-,-,-};
for(e = ; e <= g ;e++)
{
for(ee = ; ee < ; ee++)
{
int tx = xx+dd[ee][];
int ty = yy+dd[ee][];
if(judge(tx,ty))
{
int oo = bfs(x[e],y[e],tx,ty,);
if(oo!=INF)
{
o[tx][ty][x[e]][y[e]] = oo;
o[x[e]][y[e]][tx][ty] = oo;
}
}
}
}
int dis = INF;
for(i = ; i <= n ; i++)
for(j = ; j <= m ; j++)
{
if(bfs(i,j,,,)<)
continue;
int ko = bfs(i,j,,,);
int tns = ko+max(abs(i-xx),abs(j-yy));
if(tns<ans)
ans = tns; if(g==)
ans = ko;
for(e = ; e <= g ;e++)
{
for(ee = ; ee < ; ee++)
{
int tx = xx+dd[ee][];
int ty = yy+dd[ee][];
int o1 = o[x[e]][y[e]][tx][ty],o2 = o[i][j][tx][ty],o3 = o[i][j][x[e]][y[e]];
if(o1==INF||o2==INF||o3==INF)
continue;
if(judge(tx,ty)&&ans>(o1+o2-o3+ko+max(abs(tx-xx),abs(ty-yy))))
{
ans = o1+o2-o3+ko+max(abs(tx-xx),abs(ty-yy));
}
}
}
}
cout<<ans<<endl;
return ;
}