洛谷 P1930 亚瑟王的宫殿 Camelot

传送门

题目大意：棋盘有骑士有王，让所有点跳到一个点，求所有棋子跳的步数和，和最小。

题解：bfs+枚举

王的人生：

1):自己走到聚集点

2):某个骑士来到王这里，两个棋子一起到聚集点

3):王走几步，遇到骑士，再一起到聚集点

枚举聚集点O(nm),枚举去王那里的骑士O(nm*num),枚举

相遇的点O((nm)^2*num),假设骑士是n*m个，那么时间复

杂度是O((nm)^3)....时间复杂度绝对不行....

模拟一下发现，骑士和国王相遇的点，肯定在国王周围很近

的格子,所以枚举相遇的点复杂度不是O(nm)而是O(几乎没有)

BFS预处理每个点到每个点的最短距离dis[][][][]，sum[i][j],表示聚集

点在(i,j)所有骑士都到(i,j)的距离和kingdis[i][j]表示国王到(i,j)的距离。

最后的距离公式是

所有骑士到枚举的聚集点的距离-枚举的骑士到聚集点的距离+枚举的骑

士相遇点的距离+相遇点的距离到聚集点的距离+国王到相遇点的距离。

时间复杂度是O(AC) O(8nm+nm*numk)..我猜的

错因：最后的距离公式加晕头了，少加了一项。dis数组没有初始化，有些点不能跳到某些点。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define inf 2147483647

#define maxn 50

using namespace std;

char s[];

int n,m,x,num,ans;

int dis[maxn][maxn][maxn][maxn],king_dis[maxn][maxn];

int vis[maxn][maxn],sum[maxn][maxn];

int mx[]={-,-,-,-,,,,},

    my[]={,-,,-,,-,,-};

struct node{

    int x,y,ste;

};

queue<node>q;

struct Node{

    int x,y;

}king,kni[maxn*maxn];

void BFS(int x,int y){

    memset(vis,,sizeof(vis));

    while(!q.empty())q.pop();

    vis[x][y]=true;

    node now;now.x=x;now.y=y;now.ste=;

    dis[x][y][x][y]=;

    q.push(now);

    while(!q.empty()){

        node now=q.front();q.pop();

        int nx=now.x,ny=now.y,ste=now.ste;

        for(int i=;i<;i++){

            int nxtx=nx+mx[i],nxty=ny+my[i];

            if(nxtx<||nxty<||nxtx>n||nxty>m||vis[nxtx][nxty])continue;

            dis[x][y][nxtx][nxty]=dis[x][y][nx][ny]+;

            vis[nxtx][nxty]=true;

            node tmp;tmp.x=nxtx;tmp.y=nxty;tmp.ste=ste+;

            q.push(tmp);

        }

    }

}

int main(){

    scanf("%d%d",&n,&m);ans=inf;

    scanf("%s%d",s,&x);king.x=x;king.y=s[]-'A'+;

    while(scanf("%s%d",s,&x)!=EOF){

        kni[++num].x=x;kni[num].y=s[]-'A'+;

    }

    memset(dis,0x3f,sizeof(dis));

    for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      BFS(i,j);

    for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      for(int k=;k<=num;k++)

       sum[i][j]+=dis[kni[k].x][kni[k].y][i][j];

    for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      king_dis[i][j]=max(abs(king.x-i),abs(king.y-j));

    for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      ans=min(ans,sum[i][j]+king_dis[i][j]);

    for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

        for(int k=;k<=num;k++)

          for(int nx=king.x-;nx<=king.x+;nx++)

            for(int ny=king.y-;ny<=king.y+;ny++)

              if(nx<||ny<||nx>n||ny>m)continue;

               else ans=min(ans,sum[i][j]-dis[kni[k].x][kni[k].y][i][j]+dis[kni[k].x][kni[k].y][nx][ny]+dis[nx][ny][i][j]+king_dis[nx][ny]);

    printf("%d\n",ans);

    return ;

}