骑士问题

/*骑士问题*/
#include <iostream>
#include <string>
//#include <fstream>
#include <queue>
using namespace std;
#define MAX 12

typedef struct _point
{
        int x;
        int y;
        int dep;
}point;

int map[MAX][MAX];
int p[][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
point start,end;
//fstream fin;

int bfs();
int main()
{  
   //fin.open("2585.txt",ios::in);
   int times=0;
   int b;
   while(cin>>b)
   {
       if(b==-1) break;
       for(int i=0;i<12;i++)
          for(int j=0;j<12;j++)
             map[i][j]=1;
       //周围围上栅栏 
       for(int i=2;i<10;i++)
          for(int j=2;j<10;j++)
            map[i][j]=0;
       
       string a;
       for(int i=0;i<b;i++)
       {
                cin>>a;
                map[a[0]-'a'+2][(a[1]-'1')+2]=1;
       } 
  
       cin>>a;
       start.x=a[0]-'a'+2;
       start.y=a[1]-'1'+2;
       start.dep=0;
       
       
       cin>>a;
       end.x=a[0]-'a'+2;
       end.y=a[1]-'1'+2;
       
       int dep=bfs();
       if(dep)
         cout<<"Board "<<++times<<":"<<dep<<" moves"<<endl; 
       else
          cout<<"Board "<<++times<<":not reachable"<<endl;
   }
   system("pause");
   return 0;
}

int bfs()
{
    int dep=0;
    queue<point> Q;
    Q.push(start);
    while(!Q.empty())
    {
          //当前是的dep 
           for(int i=0;i<8;i++)
           {
                   point cur=Q.front();
                   if(map[cur.x+p[i][0]][cur.y+p[i][1]]==0)
                   {
                         if(end.x==cur.x+p[i][0]&&cur.y+p[i][1]==end.y)
                         {
                              end.dep=cur.dep+1;
                              return end.dep;
                         }
                         map[cur.x+p[i][0]][cur.y+p[i][1]]=1;
                         point temp;
                         temp.x=cur.x+p[i][0];
                         temp.y=cur.y+p[i][1];
                         temp.dep=cur.dep+1;
                         Q.push(temp);
                   }
           }
          
           Q.pop();         
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：树中两个结点的最低公共祖先
下一个：HDOJ/HDU---1874 畅通工程续 最短路（dijkstra）