USACO Section 3.3 Camelot - 略恶心的BFS

这题的意思是找到最少的时间和使所有Knight和King到达一个格子...但蛋疼的是King不仅可以按平时的规则走...在和Knight相遇后可以和骑士合体一起走...=.=.....

先做好两两点之间通过Knight的步伐能走到的最短时间这里可以打出一个表..4维的..arc[x1][y1][x2][y2] 代表(x1,y1)到(x2,y2)的"Knight"最短距离....再开始枚举每个点..枚举每个点时又枚举是王自己走过去还是王走几步后和哪个骑士一起过去...好吧..其实我的程序也是大概来猜测的..给了King最多4步的移动空间~~但似乎还是可以过所有数据的...

Program:

/*  
ID: zzyzzy12   
LANG: C++   
TASK: camelot
*/      
#include<iostream>      
#include<istream>  
#include<stdio.h>      
#include<string.h>      
#include<math.h>      
#include<stack>  
#include<algorithm>      
#include<queue>   
#define oo 1000000000  
#define ll long long   
using namespace std;
struct node
{
     int x,y,w;  
}h,k,king,knight[1000];
queue<node> myqueue;
int R,C,p,arc[33][33][33][33],kingm[33][33],num; 
int move[2][8][2]={{{1,0},{1,1},{0,1},{-1,1},{-1,0},{1,-1},{0,-1},{-1,-1}},
                   {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}}}; 
int getdata()
{
      char c='1';
      while (c<'A' || c>'Z' )
         if (scanf("%c",&c)==EOF) return 0; 
      return c-'A'+1;   
} 
void make(node hh,int tp)
{       
      h=hh;  
      arc[hh.x][hh.y][h.x][h.y]=0;
      myqueue.push(h);
      while (!myqueue.empty())
      {
             h=myqueue.front();  
             myqueue.pop();
             for (p=0;p<8;p++)
             {
                     k.x=h.x+move[tp][p][0];  
                     k.y=h.y+move[tp][p][1];
                     if (k.x<1 || k.y<1 || k.x>C || k.y>R) continue; 
                     if (arc[hh.x][hh.y][k.x][k.y]==-1)
                     {
                            k.w=h.w+1; 
                            myqueue.push(k);        
                            arc[hh.x][hh.y][k.x][k.y]=k.w;             
                     }               
             }    
      }  
}
void makekingmove()
{       
      h=king; 
      kingm[h.x][h.y]=0;
      myqueue.push(h);
      while (!myqueue.empty())
      {
             h=myqueue.front();  
             myqueue.pop();
             for (p=0;p<8;p++)
             {
                     k.x=h.x+move[0][p][0];  
                     k.y=h.y+move[0][p][1];
                     if (k.x<1 || k.y<1 || k.x>C || k.y>R) continue; 
                     if (kingm[k.x][k.y]==-1)
                     {
                            k.w=h.w+1; 
                            myqueue.push(k);        
                            kingm[k.x][k.y]=k.w;             
                     }               
             }    
      }  
}
int getanswer()
{
      int x,y,p,i,j,m,k,t,v,ans=oo; 
      for (x=1;x<=C;x++)
         for (y=1;y<=R;y++)
         {
                 m=kingm[x][y];
                 for (i=1;i<=num;i++)
                   if (arc[knight[i].x][knight[i].y][x][y]==-1) goto A;
                     else m+=arc[knight[i].x][knight[i].y][x][y];
                 if (m<ans) ans=m;
                 for (t=0;t<5;t++)
                 for (v=0;v<8;v++)
                 {
                        i=move[0][v][0]*t+king.x; j=move[0][v][1]*t+king.y;
                        if (i<1 || j<1 || i>C || j>R) continue;
                        if (arc[i][j][x][y]!=-1)
                        {
                              for (p=1;p<=num;p++)
                              if (arc[knight[p].x][knight[p].y][i][j]!=-1)
                              {
                                    k=m-kingm[x][y]-arc[knight[p].x][knight[p].y][x][y]+arc[knight[p].x][knight[p].y][i][j]+arc[i][j][x][y]+kingm[i][j];
                                    if (k<ans) ans=k; 
                              }
                        }
                 }  
                 A: ;
         }
      return ans;    
}
int main()  
{  
      freopen("camelot.in","r",stdin);    
      freopen("camelot.out","w",stdout);  
      while (!myqueue.empty()) myqueue.pop(); 
      memset(arc,-1,sizeof(arc));   
      memset(kingm,-1,sizeof(kingm));
      scanf("%d%d",&R,&C);  
      king.x=getdata(); scanf("%d",&king.y); king.w=0;   
      makekingmove();
      for (int x=1;x<=C;x++)
        for (int y=1;y<=R;y++)
        {
              h.x=x; h.y=y; h.w=0;
              make(h,1);    
        }
      num=0;
      while (1)
      { 
              h.x=getdata(); 
              if (!h.x) break;
              scanf("%d",&h.y); h.w=0;   
              knight[++num]=h;
      }    
      printf("%d\n",getanswer());
      return 0;     
}