POJ1178枚举三个地方（所有点都去同一个点）

题意：
      有一个国王和很多骑士，他们都要到某一个点去集合，然后问所有人都到达某个终点的距离和最小是多少？过程中如果国王遇到了一个骑士的话，国王就可以和骑士一起按照骑士的走法走，这是两个人算一个人，同时国王有八种走法，骑士也有八种走法，两个不一样。


思路：

      可以枚举终点，和骑士相交的点还有和那个骑士相交，只要确定这三个点后距离就出来了，求距离可以用广搜预处理，也可以用最短路预处理，不管用什么记得细心点，还有对于国王的最短路直接可以算出来，就是max(abs(x1-x2),abs(y1-y2))。

#include<queue>
#include<stdio.h>
#include<string.h>

#define N 70
#define INF 1000000000

using namespace std;

typedef struct
{
    int x ,y ,t;
}NODE;

NODE xin ,tou;
NODE node[N];
int dis[N][N];
int mark[N];
int dir[8][2] = {1 ,2 ,1 ,-2 ,-1 ,2 ,-1 ,-2 ,2 ,1 ,2 ,-1 ,-2 ,1 ,-2 ,-1};


int minn(int x ,int y)
{
    return x < y ? x : y;
}

int maxx(int x ,int y)
{
    return x > y ? x : y;
}

int abss(int x)
{
    return x > 0 ? x : -x;
}

bool ok(int x ,int y)
{
    return x >= 1 && x <= 8 && y >= 1 && y <= 8 && !mark[(x-1)*8+y];
}

void BFS(int x ,int y)
{
    queue<NODE>q;
    xin.x = x ,xin.y = y ,xin.t = 0;
    memset(mark ,0 ,sizeof(mark));
    mark[(x-1)*8+y] = 1;
    dis[(x-1)*8+y][(x-1)*8+y] = 0;
    q.push(xin);

    while(!q.empty())
    {
        tou = q.front();
        dis[(x-1)*8+y][(tou.x-1)*8+tou.y] = tou.t;
        q.pop();
        for(int i = 0 ;i < 8 ;i ++)
        {
            xin.x = tou.x + dir[i][0];
            xin.y = tou.y + dir[i][1];
            xin.t = tou.t + 1;
            if(ok(xin.x ,xin.y))
            {
                mark[(xin.x-1)*8+xin.y] = 1;
                q.push(xin);
            }
        }
    }
    return ;
}


int main ()
{
    char str[150];
    int i ,j ,k ,x ,y;
    for(i = 1 ;i <= 8 ;i ++)
    for(j = 1 ;j <= 8 ;j ++)
    BFS(i ,j);
    while(~scanf("%s" ,str))
    {
        int len = strlen(str);
        int id = 0;
        for(i = 0 ;i < len ;i += 2)
        {
            x = str[i+1] - '0';
            y = str[i] - 'A' + 1;
            node[++id].x = x;
            node[id].y = y;
        }
        int ans = INF;
        for(i = 1 ;i <= 64 ;i ++) //终点
        for(j = 1 ;j <= 64 ;j ++) //相遇点
        for(k = 2 ;k <= id ;k ++) //相遇的那个骑士
        {
            int s = 0;
            x = (j-1) / 8 + 1;
            y = j % 8;
            if(!y) y = 8;
            s = maxx(abss(x - node[1].x),abss(y - node[1].y));
            s += dis[(node[k].x - 1) * 8 + node[k].y][j];
            s += dis[j][i];
            for(int w = 2 ;w <= id ;w ++)
            {
               if(w == k) continue;
               s += dis[(node[w].x-1)*8+node[w].y][i];
            }
            if(s < ans) ans = s;
        }
        if(id == 1) ans = 0;
        printf("%d
" ,ans);
    }
    return 0;

}