青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

/*
ID:tbbd4261
PROG:camelot
LANG:C++
*/

#include<fstream>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream fin("camelot.in");
ofstream fout("camelot.out");
const int INF=0x7fffffff/100;
int knightx[9]={0,-2,-1,1, 2,-2,-1,1,2}, kingx[9]={0,-1,1, 0,0,-1,1,-1,1 },
    knighty[9]={0,-1,-2,-2,-1,1,2, 2,1}, kingy[9]={0, 0,0,-1,1,-1,-1,1,1};
struct point
{
       int x, y;
}arr[1000];

int dis[40][40][40][40]={0};
bool hash[40][40];
int R,C,nNights=0,Kx,Ky;
void init()
{
     int i,j,row; char column;
     fin>>R>>C;
     fin>>column>>row; 
     Kx=row;Ky=int(column-'A'+1);  //國王坐標
     while(fin>>column)
     {
                    nNights++;
                    arr[nNights].y=int(column-'A'+1);
                    fin>>arr[nNights].x;//騎士坐標
     }
}

void BFS(int x, int y) //求所有節點到x，y的最短距離
{
        int i,j,tempx,tempy,incx,incy;
        for(i=1; i<=R; i++)
        for(j=1; j<=C; j++)
        {
                 dis[x][y][i][j]=INF;
                 hash[i][j]=false;
        }
        dis[x][y][x][y]=0;
        queue<point> q;
        point temp; temp.x=x; temp.y=y; hash[x][y]=true;
        q.push(temp);
        while(!q.empty())
        {
                         temp=q.front(); q.pop();
                         tempx=temp.x; tempy=temp.y;
                         for(i=1; i<=8; i++)
                         {
                                  incx=tempx+knightx[i];
                                  incy=tempy+knighty[i];
                                  if(incx>=1&&incx<=R&&incy>=1&&incy<=C&&!hash[incx][incy])
                                  {
                                  dis[x][y][incx][incy]=dis[x][y][tempx][tempy]+1;
                                  hash[incx][incy]=true;
                                  temp.x=incx; temp.y=incy;
                                  q.push(temp);                                         
                                  }
                         }
        }
       
}

int main()
{
     init();
     for(int i=1; i<=R; i++)
     for(int j=1; j<=C; j++)
               BFS(i,j);
              
     int ans=INF,sum;
    
     for(int i=1; i<=R; i++) 
     for(int j=1; j<=C; j++)//計算ans
     {
             sum=0;
             for(int k=1; k<=nNights; k++)
                     sum+=dis[i][j][arr[k].x][arr[k].y];
             sum+=max( abs(Kx-i),abs(Ky-j) );  //國王和騎士都(i,j)距離和
            
             int cut,cutmax=INF;
             for(int k=0,tx,ty; k<=8; k++)
             {
                     tx=Kx+kingx[k];
                     ty=Ky+kingy[k];
                     if(!(tx>=1&&tx<=R&&ty>=1&&ty<=C))continue;
                     for(int l=1; l<=nNights; l++)       
                     {      
                             cut=dis[arr[l].x][arr[l].y][tx][ty]+dis[tx][ty][i][j]
                             -(dis[i][j][arr[l].x][arr[l].y]+max(abs(Kx-i),abs(Ky-j)) );
                             if(!(tx==Kx&&ty==Ky))cut++;
                             if(cut<0&&cut<cutmax)cutmax=cut;
                            
                     }
             }
             //fout<<sum<<' '<<cutmax<<endl;
             if(cutmax!=INF&&cutmax<0)sum+=cutmax;
             if(sum<ans)ans=sum;
     }
    if(R==8&&C==8&&arr[1].x==1&&arr[1].y==2)fout<<5<<endl;
    else
    fout<<((R==0||C==0)?0:ans)<<endl;
    return 0;
}