USACO Camelot

看到这个题目最先想到的是最短路问题，即求出每个点对之间骑士跳跃的最小路程和国王移动到每个点的最短路程，由于是不加权的无向图，因此使用BFS就足够快了，用Floyd貌似有些小题大作。

然后，我就不知道下一步如何做了，因为我误解题目的意思了，各位请看：

whenever the king and one or more knights are placed in the same square, the player may choose to move the king and one of the knights together from that point on, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move.

本人注意到了那个“more”，却忽视了下面的“one of”，如果真的这样，这个问题就变成了NP问题（不知这样说是否严谨），自然是难以解决的。

看到了“one of”，那个“more”就几乎没有任何意义了，题目的难度随之迅速降低——使用两重枚举就可以解决问题。

这题的输入格式有些特殊（换行符尤其讨厌），因此用上了ctype库，不知各位是否有更好的方案。

此外，当棋盘很小时，会出现骑士不能走到的点，要考虑到这种情况。

关于INF的问题：虽然有LONG_MAX，但是很多时候一不小心漏了判断就容易溢出，因此自己定义INF更方便一些，不过个人认为LONG_MAX更规范。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define INF 1000000

typedef struct position_T
{
    int x,y;
}position_T;

position_T king,knight[26 * 30 + 10];
int cnt = 0;
int r,c;
int jx[8] = {1,1,-1,-1,2,2,-2,-2};
int jy[8] = {2,-2,2,-2,1,-1,1,-1};
int mx[8] = {0,0,1,1,1,-1,-1,-1};
int my[8] = {1,-1,0,-1,1,0,1,-1};
long jdist[31][31][31][31];    //棋盘上两点间的跳跃最短路
long king_dist[31][31];     //国王到每一点的最短路

int get_min(int a,int b)
{
    if(a < b)
        return a;
    return b;
}

void init()
{
    char tx;
    scanf("%d%d\n",&r,&c);
    scanf("%c%d\n",&tx,&king.y);
    king.y -= 1;
    king.x = tx - 'A';
    cnt = 0;
    while(!feof(stdin))
    {
        tx = getchar();
        if(isalpha(tx))
        {
            scanf("%d",&knight[cnt].y);
            knight[cnt].y --;
            knight[cnt].x = tx - 'A';
            cnt ++;
        }
    }
}

typedef struct Qnode
{
    int x,y;
}Qnode;

Qnode queue[26 * 30 + 10];
int head,tail;

void enqueue(int x,int y)
{
    queue[tail].x = x;
    queue[tail].y = y;
    tail ++;
}

Qnode dequeue()
{
    return queue[head ++];
}

void jbfs(int sx,int sy)  //计算jdist数组
{
    int i,j,k,x,y;
    head = tail = 0;
    for(i = 0;i < c;i ++)
        for(j = 0;j < r;j ++)
            jdist[sx][sy][i][j] = INF;
    jdist[sx][sy][sx][sy] = 0;
    enqueue(sx,sy);
    Qnode now;
    while(head < tail)
    {
        now = dequeue();
        for(k = 0;k < 8;k ++)
        {
            x = now.x + jx[k];
            y = now.y + jy[k];
            if((x >= 0) && (x < c) && (y >= 0) && (y < r) && jdist[sx][sy][x][y] == INF)
            {
                jdist[sx][sy][x][y] = jdist[sx][sy][now.x][now.y] + 1;
                enqueue(x,y);
            }
        }
    }
}

void king_bfs()    //计算king_dist数组
{
    int i,j,k,x,y;
    head = tail = 0;
    x = king.x;
    y = king.y;
    for(i = 0;i < c;i ++)
        for(j = 0;j < r;j ++)
            king_dist[i][j] = INF;
    king_dist[x][y] = 0;
    enqueue(x,y);
    Qnode now;
    while(head < tail)
    {
        now = dequeue();
        for(k = 0;k < 8;k ++)
        {
            x = now.x + mx[k];
            y = now.y + my[k];
            if((x >= 0) && (x < c) && (y >= 0) && (y < r) && king_dist[x][y] == INF)
            {
                king_dist[x][y] = king_dist[now.x][now.y] + 1;
                enqueue(x,y);
            }
        }
    }
}

long solve(int x,int y)   //计算所有在(x,y)点汇集的最小步数
{
    int i,j,k;
    long res = INF;
    long dist_part = 0;  //所有骑士跳跃到该店的最小步数和
    long pick_dist = INF;  //某个骑士去“接”国王相对于直接到达（x，y）点多走的步数
    for(i = 0;i < cnt;i ++)
    {
        //printf("%d:%ld\n",i,jdist[knight[i].x][knight[i].y][x][y]);
        dist_part += jdist[knight[i].x][knight[i].y][x][y];
        if(jdist[knight[i].x][knight[i].y][x][y] == INF)    return INF;
    }
    for(i = 0;i < c;i ++)
        for(j = 0;j < r;j ++)
        {
            if(king_dist[i][j] > 4)    continue;  //国王走太远就不考虑了
            for(k = 0;k < cnt;k ++)   //对每个骑士进行枚举，算出pick_dist的最小值
            {
                if(king_dist[i][j] + jdist[knight[k].x][knight[k].y][i][j] + jdist[i][j][x][y] - jdist[knight[k].x][knight[k].y][x][y] >= 0)
                    pick_dist = get_min(pick_dist,king_dist[i][j] + jdist[knight[k].x][knight[k].y][i][j] + jdist[i][j][x][y] - jdist[knight[k].x][knight[k].y][x][y]);
            }
        }
    res = get_min(dist_part + king_dist[x][y],dist_part + pick_dist);
    //还要考虑王自己走到(x,y)的情况，取最小值
    return res;
}

int main()
{
    int i,j;
    long ans = INF;
    freopen("camelot.in","r",stdin);
    freopen("camelot.out","w",stdout);
    init();
    for(i = 0;i < c;i ++)
        for(j = 0;j < r;j ++)
            jbfs(i,j);
    king_bfs();
   
    for(i = 0;i < c;i ++)
        for(j = 0;j < r;j ++)
        {
            ans = get_min(ans,solve(i,j));  //枚举汇合点，取最小值作为结果
        }
   
    printf("%ld\n",ans);
    return 0;
}