Knight Moves

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy. 
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part. 

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b. 

Input

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. 

Output

For each test case, print one line saying "To get from xx to yy takes n knight moves.". 

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.

分析:广度优先搜索题

题意如图所示:一个棋子(骑士)可以有八个方向走,广搜确定最小的走的步数。

 

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
struct node
{
     int c;
     int r;
     int lev;
}front,tmp,start,end;
    queue <node>Q;
    int a[]={0,-2,-2,-1,-1,1,1,2,2};
    int b[]={0,-1,1,-2,2,-2,2,-1,1};
int GetRe(node s,node e){
    int i;
    
    while(!Q.empty())
        Q.pop();
        
        
    if(e.c==s.c&&e.r==s.r)return 0;//达到目标
        Q.push(s);
        
        
    while(!Q.empty()){
        front=Q.front();
        Q.pop();
        for(i=1;i<=8;i++)
        {
            tmp.c=b[i]+front.c;
            tmp.r=a[i]+front.r;
            tmp.lev=front.lev+1;
            if(e.c==tmp.c&&e.r==tmp.r)
                return tmp.lev;
            if(tmp.c>=1&&tmp.c<=8&&tmp.r>=1&&tmp.r<=8)
                Q.push(tmp);
        }
     }
     return 0;
}
    int main()
    {   char s[3],e[3];
        while(scanf("%s %s",s,e)!=EOF){

                start.c=s[0]-'a'+1;
                start.r=s[1]-'0';
                start.lev=0;
                end.c=e[0]-'a'+1;
                end.r=e[1]-'0';
                printf("To get from %s to %s takes %d knight moves.\n",s,e,GetRe(start,end));

        }

       // cout << "Hello world!" << endl;
        return 0;
}

 

全部评论

相关推荐

07-14 13:37
重庆大学 C++
点赞 评论 收藏
分享
Hakasee:我的简历和你的基本一样,上周去了上海,boss投了三百家, 三家线下面试 第一家没有做题,全是八股和项目,因为第一次面试不怎么熟练,挂了 第二家,给你几个题目(①css垂直居中文字,字体每两秒闪烁一下以及点击弹窗,②给你一个链接,实现可视化地图,③然后是八股,图片性能优化,以及对图片app有什么想法),45分钟内做完,然后老板面试) 第三家特别偏僻,有点阴森,到了之后让了一个工位给我,有四个题目,①格式化时间 年月日当前时间星期几② 正则表达式提取新闻文字,③在文本域输入文字生成选择题以及选项④生成商品排版还是什么来着 三家都是不超过50人的小公司 两家线上牛客笔试(卡伦特,七牛云,但是笔试不仅要考前端,还要考后端,算法,甚至数学题 我的建议是如果只做了这两个vue项目且不怎么熟练的情况下,先沉淀沉淀,把react学了,上海好的公司基本都是react查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务