knight.cpp

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

#include<fstream>
using namespace std;

ifstream in("knight.in");
ofstream out("knight.out");

struct node{ int x,y;};
int    visited[8][8];
int    dir[8][2]={{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};

int bfs(int xs,int ys,int xt,int yt)
{
   node queue[64],tnode;
   int  head,tail,ttail;
   int  i,k,step=0;

   head=0;
   tail=1;
   queue[head].x=xs;
   queue[head].y=ys;
   visited[xs][ys]=1;
   while(head<tail){
      step++;
	  ttail=tail;
	  for(k=head;k<tail;k++){
		  for(i=0;i<8;i++){
		     tnode.x=queue[k].x+dir[i][0];
			 tnode.y=queue[k].y+dir[i][1];
			 if(tnode.x>=0 && tnode.x<8 && tnode.y>=0 && tnode.y<8 
				 && !visited[tnode.x][tnode.y]){
			    queue[ttail].x=tnode.x;
				queue[ttail++].y=tnode.y;
				visited[tnode.x][tnode.y]=1;
				if(visited[xt][yt]) return step;
			 }
		  }
	  }
	  head=tail;
	  tail=ttail;
   }
   return -1;
}

int main()
{
   int  cases,i,j,b,ans;
   char ch_1,ch_2;
   int  xs,ys,xt,yt;
   
   cases=0;
   while(in>>b){
     if(b==-1) break;
	 cases++;
	 for(i=0;i<8;i++) 
		 for(j=0;j<8;j++)
			 visited[i][j]=0;
     for(i=0;i<b;i++){
	     in>>ch_1>>ch_2;
		 visited[ch_1-'a'][ch_2-'1']=1;
	 }
	 in>>ch_1>>ch_2;
	 xs=ch_1-'a';
     ys=ch_2-'1';
	 in>>ch_1>>ch_2;
	 xt=ch_1-'a';
	 yt=ch_2-'1';
	 ans=bfs(xs,ys,xt,yt);
	 out<<"Board "<<cases<<": ";
	 if(ans==-1) out<<"not reachable"<<endl;
	 else out<<ans<<" moves"<<endl;
   }
   return 0;
}