Camelot

Description

Centuries ago, King Arthur and the Knights of the Round Table used to meet every year on New Year's Day to celebrate their fellowship. In remembrance of these events, we consider a board game for one player, on which one king and several knight pieces are placed at random on distinct squares. 
The Board is an 8x8 array of squares. The King can move to any adjacent square, as shown in Figure 2, as long as it does not fall off the board. A Knight can jump as shown in Figure 3, as long as it does not fall off the board. 

During the play, the player can place more than one piece in the same square. The board squares are assumed big enough so that a piece is never an obstacle for other piece to move freely. 
The player's goal is to move the pieces so as to gather them all in the same square, in the smallest possible number of moves. To achieve this, he must move the pieces as prescribed above. Additionally, 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 henceforth, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move. 

Write a program to compute the minimum number of moves the player must perform to produce the gathering. 

Input

Your program is to read from standard input. The input contains the initial board configuration, encoded as a character string. The string contains a sequence of up to 64 distinct board positions, being the first one the position of the king and the remaining ones those of the knights. Each position is a letter-digit pair. The letter indicates the horizontal board coordinate, the digit indicates the vertical board coordinate. 

0 <= number of knights <= 63

Output

Your program is to write to standard output. The output must contain a single line with an integer indicating the minimum number of moves the player must perform to produce the gathering.

Sample Input

D4A3A8H1H8

Sample Output

10
  
题目大意：在一个8*8的棋盘上有一个国王和若干个骑士，问国王和骑士全部走到一个格子里最少的总步数是多少
  
国王和骑士的每一步的走法分别如上图2和3所示，并且如果国王遇到一个骑士，骑士就可以载上国王一起走（注意并不是多个骑士啊，即如果国王和多个骑士走到一格也只有一个骑士上国王）
  
  
思路：
  
先求出国王和骑士分别从一个点到另一个点的最少步数（我用的floyd，也可以用广搜）
  
然后枚举终点，哪一个骑士去接国王，国王和骑士相遇点，看哪种组合总步数最少（64*64*64）
  
  
24号晚上在寝室做这个题真是出各种错，有几天没做题手残就加重了，连什么i，j打反了都出现了于是那天将近折腾了将近一个晚上一直到熄灯都还WA着呢……（于是我会说我在梦中跳了几天的棋盘格子吗？o(╯□╰)o）
  
今天读一遍发现果然脑残啊啊啊，在处理那个国王一步就能到达的点的时候左右两个方向写掉了……果然那个一步就能走的方向一个一个判断是个极度不科学的事情，还是应该弄成一个常量数组用循环的（这样的话记得给图加上边框！）
  
代码改来改去简直都要不能忍了！！
  
   
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 2147483647;

long n, king;
long knights[100];

long f[100][100];
long g[100][100];

inline long min(long a, long b)
{
    return a > b ? b : a;
}

void prepare()
{
    memset(f, 127, sizeof(f));

    for (long i = 1; i <= 8; i++)
    for (long j = 1; j <= 8; j++)
    {
        long t1 = (i - 1) * 8 + j;
        if (i >= 3)
        {
            if (j >= 2)
            {
                long t2 = (i - 3) * 8 + j - 1;
                f[t1][t2] = f[t2][t1] = 1;
            }
            if (j <= 7)
            {
                long t2 = (i - 3) * 8 + j + 1;
                f[t1][t2] = f[t2][t1] = 1;
            }
        }

        if (i >= 2)
        {
            if (j >= 3)
            {
                long t2 = (i - 2) * 8 + j - 2;
                f[t1][t2] = f[t2][t1] = 1;
            }
            if (j <= 6)
            {
                long t2 = (i - 2) * 8 + j + 2;
                f[t1][t2] = f[t2][t1] = 1;
            }

        }

        if (i <= 8)
        {
            if (j >= 3)
            {
                long t2 = i * 8 + j - 2;
                f[t1][t2] = f[t2][t1] = 1;
            }
            if (j <= 6)
            {
                long t2 = i * 8 + j + 2;
                f[t1][t2] = f[t2][t1] = 1;
            }

        }

        if (i <= 7)
        {
            if (j >= 2)
            {
                long t2 = (i + 1) * 8 + j - 1;
                f[t1][t2] = f[t2][t1] = 1;
            }
            if (j <= 7)
            {
                long t2 = (i + 1) * 8 + j + 1;
                f[t1][t2] = f[t2][t1] = 1;
            }
        }

    }


    memset(g, 127, sizeof(g));
    for (long i = 1; i <= 8; i++)
    for (long j = 1; j <= 8; j++)
    {
        long t1 = (i - 1) * 8 + j;
        if (i >= 2)
        {
            long t2 = (i - 2) * 8 + j;
            g[t1][t2] = g[t2][t1] = 1;
            if (j >= 2)
            {
                long t2 = (i - 2) * 8 + j - 1;
                g[t1][t2] = g[t2][t1] = 1;
            }
            if (j <= 7)
            {
                long t2 = (i - 2) * 8 + j + 1;
                g[t1][t2] = g[t2][t1] = 1;
            }
        }

        if (i <= 7)
        {
            long t2 = i * 8 + j;
            g[t1][t2] = g[t2][t1] = 1;
            if (j >= 2)
            {
                long t2 = i * 8 + j - 1;
                g[t1][t2] = g[t2][t1] = 1;
            }
            if (j <= 7)
            {
                long t2 = i * 8 + j + 1;
                g[t1][t2] = g[t2][t1] = 1;
            }
        }
        if (j >= 2)
        {
            long t2 = (i - 1) * 8 + j - 1;
            g[t1][t2] = g[t2][t1] = 1;
        }
        if (j <= 7)
        {
            long t2 = (i - 1) * 8 + j + 1;
            g[t1][t2] = g[t2][t1] = 1;
        }

    }


}
void floyd1()
{
    for (long i = 1; i <= 64; i++)
        f[i][i] = 0;
    for (long k = 1; k <= 64; k++)
        for (long i = 1; i <= 64; i++)
            for (long j = 1; j <= 64; j++)
            {
                if ((i != j) && (j != k) && (k != i))
                {
                    if ((f[i][k] < 10000)&& (f[k][j] < 10000))
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }

}

void floyd2()
{
    for (long i = 1; i <= 64; i++)
        g[i][i] = 0;
    for (long k = 1; k <= 64; k++)
        for (long i = 1; i <= 64; i++)
            for (long j = 1; j <= 64; j++)
            {
                if ((i != j) && (j != k) && (k != i))
                {
                    if ((g[i][k] < 10000)&& (g[k][j] < 10000))
                        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                }

            }

}

long solve(long x,long y)
///最后在x点汇合且有一个骑士在y点遇上国王(实际上包含了国王自己走到汇合点的方案)
{
    long ret = INF;
    for (long i = 1; i <= n; i++)  ///枚举接国王的骑士是哪一个
    {
        long sum = 0 ;
        sum += f[knights[i]][y] + g[king][y] + f[y][x];
        for (long j = 1; j <= n; j++)
        {
            if (i != j)
                sum += f[knights[j]][x];
        }
        ret = min(ret, sum);
    }
    return ret;
}
int main()
{
    char c[200];
    scanf("%s", c);

    long x = (c[0] - 'A') + 1;
    long y = (c[1] - '0');
    king = (x  - 1) * 8 + y;
    long k = 1;
    for (long i = 2; i < strlen(c); i += 2)
    {
        x = (c[i] - 'A') + 1;
        y = (c[i + 1] - '0');
        knights[k] =  (x  - 1) * 8 + y;
        k++;
    }

    n = k - 1;
    prepare();
    floyd1();
    floyd2();
    long re = INF;
    for (long i = 1; i <= 64; i++)
    {
        long t = INF;
        for (long j = 1; j <= 64; j++)
        {
            t = min(t, solve(i, j));
        }
        if (t < re) re = t;
    }
    printf("%d\n", re);

    return 0;
}