poj1778

在一个 8*8 的棋盘里有一个国王和一些骑士，我们要把他们送到同一顶点上去。 国王能
够选择一名骑士作为坐骑，而与骑士一起行动（相当于一个骑士），同一位置， 同一时刻可
以有多个骑士。问最少走的步数。 骑士的行动方式如下图所示。

输入格式：
仅有一行，包含一个字母和数字间隔的字符串，先字母再数字，字母仅可能是大写的 A
到 H，数字只可能是 1 到 8，描述国王和骑士的坐标位置，第一个是国王的坐标，后面都是
骑士的坐标，显然字母是列号，数字是行号。
输出格式：
仅有一个数，表示题目要求的最少步数。
样例输入： D4A3A8H1H8
样例输出： 10
数据范围：字符串的长度不会超过 128。

爆搜

枚举64个相遇点

再枚举64个国王JBSM的点

#include<iostream>

#include<cstring>

#include<cmath>

#define MN 64

#define MV 100000

#define min(a,b) a<=b?a:b

#define max(a,b) a>=b?a:b

using namespace std;

int dir[][]={{-,-},{-,-},{-,},{-,},{,-},{,-},{,},{,}};

int f[][MN+][MN+],kn[MN+][],n=,t[MN+];

bool lim(int x, int y)

{

    return x>= && x< && y>= && y<;

}

void csh()

{

    int i,j,k,t1,t2,p1,p2;

    for (i=;i<MN;i++) for (j=;j<MN;j++)

    {

        if (i==j) f[][i][j]=f[][i][j]=;

        else f[][i][j]=f[][i][j]=MV;

    }

    for (i=;i<;i++) for (j=;j<;j++) for (k=;k<;k++)

    {

        t1=i+dir[k][];t2=j+dir[k][];

        if (lim(t1,t2))

        {

            p1=i*+j;p2=t1*+t2;

            f[][p1][p2]=f[][p1][p2]=;

        }

    }

}

void floyd()

{

    int i,j,k;

    for (k=;k<MN;k++) for (i=;i<MN;i++) for (j=;j<MN;j++)

    {

        f[][i][j]=min(f[][i][k]+f[][k][j],f[][i][j]);

        f[][i][j]=min(f[][i][k]+f[][k][j],f[][i][j]);

    }

}

int main()

{

    int i,j,k,D,d1,d2,x,y,ans,king,s;

    char C[];csh();floyd();

    while (scanf("%s",C)!=EOF)

    {

        n=(strlen(C)-)/;ans=MV;

        if (n==) {cout<<;continue;}

        king=(C[]-'A')+(C[]-'')*;

        for (i=,j=;i<n;i++,j+=) t[i]=(C[j]-'A')+(C[j+]-'')*;

        for (i=;i<MN;i++)

        {

            s=;

            for (k=;k<n;k++) s+=f[][t[k]][i];

            for (j=;j<MN;j++)

            {

                d1=f[][king][j];d2=MV;

                for (k=;k<n;k++) d2=min(d2,f[][t[k]][j]+f[][j][i]-f[][t[k]][i]);

                ans=min(ans,s+d1+d2);

            }

        }

        cout<<ans<<endl;

    }

    //system("pause");

}