很明显的双向广搜,每次从M的方向搜3步,从G的方向搜1步,然后判断是否走到对方已经走过的格子即可。至于魔王的判断，直接用曼哈顿距离判断就可以了。

　　

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define MAXN 805 6 struct pnt{ 7     int x,y; 8     pnt(){}; 9     pnt(int _x,int _y):x(_x),y(_y){}10 }gst[2],st,en,q[2][MAXN*MAXN];11 int front[2],rear[2];12 int dx[4]={
   1,0,0,-1},dy[4]={
   0,1,-1,0};13 int cas,n,m,sp[2],step,gsts;14 char mz[MAXN][MAXN];15 //判断是否已经是ghost的地盘,直接用曼哈顿距离判就可以了16 int hasgst(int x,int y,int tm){17     for(int i=0;i<2;i++)if(abs(x-gst[i].x)+abs(y-gst[i].y)<=tm*2)return 1;18     return 0;19 }20 int bfs(int cur,int st,char now,char op){21     for(int k=0;k