HDU - 1372 Knight Moves

题目链接：

题目：

在象棋王国，尼古拉斯.火山是一匹英俊的马，他非常幸运迎娶了白马王国的公主，他们将度蜜月，你现在是他们的女仆，火山会问你去一些地方最少需要多少步，这么简单的事当然难不倒你。由于火山是一匹马，他的移动方式将会遵守国际象棋马的走法。

输入：

输入包含一个或多个输入样例。每个测试样例将会有两个坐标，表示现在的位置和将要到达的地方，每个坐标包含一个字母（a-h）表示列和一个数字(1-8) 行，这意味这这个象棋王国是一个8* 8的矩形。

Input

Output

每一组样例将会输出一段话 "To get from xx to yy takes n knight moves."，其中xx表示起点，yy表示终点，n为xx到yy的最短步数。

Sample Input

e2 e4

a1 b2

b2 c3

a1 h8

a1 h7

h8 a1

b1 c3

f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.

To get from a1 to b2 takes 4 knight moves.

To get from b2 to c3 takes 2 knight moves.

To get from a1 to h8 takes 6 knight moves.

To get from a1 to h7 takes 5 knight moves.

To get from h8 to a1 takes 6 knight moves.

To get from b1 to c3 takes 1 knight moves.

To get from f6 to f6 takes 0 knight moves.

思路：这道题挺坑，不咋懂象棋，百度才知道这道题的马走日走法，一开始以为一个一个走，知道这个就可以进行bfs了

//// Created by hjy on 2019/7/10.//#include
       
        #include
        
         #include
         #include
          
           #include
           
            using namespace std;typedef long long ll;struct node{    int x;    int y;    int dept;};int book[10][10];int dic[8][2]={
     {
     1,-2},{
     2,-1},{
     2,1},{
     1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};int bfs(int stx,int sty,int lax,int lay){    queue
            
             qu; node now,next; now.x=stx; now.y=sty; now.dept=0; book[stx][sty]=1; qu.push(now); while(!qu.empty()) { now=qu.front(); qu.pop(); if (now.x == lax && now.y == lay) return now.dept; for(int i=0;i<8;i++) { next.x = now.x + dic[i][0]; next.y = now.y + dic[i][1]; if (next.x < 0 || next.y < 0 || next.x>=8 || next.y>=8) continue; if (next.x>=0&&next.x<8&&next.y>=0&&next.y<8&&!book[next.x][next.y]) { book[next.x][next.y] = 1; next.dept=now.dept+1; qu.push(next); } } } return 0;}int main(){ char str[5],str1[5]; map
             
              mp; mp['a']=0; mp['b']=1; mp['c']=2; mp['d']=3; mp['e']=4; mp['f']=5; mp['g']=6; mp['h']=7; while(cin>>str) { getchar(); cin>>str1; memset(book,0,sizeof(book)); int stx=str[1]-'0'-1; int sty=mp[str[0]]; int lax=str1[1]-'0'-1; int lay=mp[str1[0]]; //cout<
              
               <<" "<
               
                <<" "<
                
                 <<" "<
                 
                  <

转载于:https://www.cnblogs.com/Vampire6/p/11167444.html

你可能感兴趣的文章