HDU - 1372 Knight Moves（bfs入门）

刺骨的言语ヽ痛彻心扉 2023-08-17 15:40 123阅读 0赞

# HDU - 1372 Knight Moves #

题目链接：[https://vjudge.net/problem/HDU-1372\#author=swust20141567][https_vjudge.net_problem_HDU-1372_author_swust20141567]

## **题目**： ##

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

输入：

输入包含一个或多个输入样例。每个测试样例将会有两个坐标，表示现在的位置和将要到达的地方，每个坐标包含一个字母（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<iostream>
    #include<queue>
    #include<map>
    #include<cstring>
    #include<cstdio>
    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<node>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<char,int>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<<stx<<" "<<sty<<" "<<lax<<" "<<lay<<endl;
    
            cout<<"To get from "<<str<<" to "<<str1<<" takes "<<bfs(stx,sty,lax,lay)<<" knight moves."<<endl;
        }
        return 0;
    }
    /*
    e2 e4
    a1 b2
    b2 c3
    a1 h8
    a1 h7
    h8 a1
    b1 c3
    f6 f6
     */

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

[https_vjudge.net_problem_HDU-1372_author_swust20141567]: https://vjudge.net/problem/HDU-1372#author=swust20141567