HDU1372,BFS象棋马走日

简单的对于bfs的运用，但是还是写的太慢了写了TMD的1H，主要是不熟悉，以后慢慢熟悉就好了，模型基本已经能建立了，主要出现bug是在方向数组的运用上面，一定要记得是从0开始的，而不是从1开始的，导致错误。

#include<cstdio>

#include<cstdlib>

#include<iostream>

using namespace std;

/*bfs*/

//方向数组

int nextx[][]={

    {-,-},

    {-,-},

    {,},

    {,},

    {,-},

    {,-},

    {-,},

    {-,}

};

/*

1 0 3 0 5 6 7 8 9

0 2 3 4 0 6 7 8 9

1 2 0 4 5 6 7 8 9

0 2 3 4 0 6 7 8 9

1 0 3 0 5 6 7 8 9

1 2 3 4 5 6 7 8 9

*/

struct que

{

    int x;//当前的A；

    int y;//当前的B；

    int step;//走过的步数

};

int main()

{

    int i;//循环变量

    int y1,y2;

    int x1,x2;

    int nowX,nowY;

    char ch[];

    int head=;

    int tail=;

    struct que ques[];

    while (gets(ch) != NULL)

    {

        //将输入的数转换成对应数字

        x1 = ch[]-'a'+;

        y1 = ch[]-'';

        x2 = ch[]-'a'+;

        y2 = ch[]-'';

        //初始化地图，用于记录走过的点

        int maps[][]={};

        head=;

        tail=;

        maps[x1][y1] = ;//记录初始点

        ques[head].x = x1;

        ques[head].y = y1;

        ques[head].step = ;

        tail++;

        nowX=x1;

        nowY=y1;

        if(nowX == x2 && nowY == y2)

        {

            goto f1;

        }

        while (head<tail)

        {

            for (i = ; i < ; i++)

            {

                nowX = ques[head].x + nextx[i][];

                nowY = ques[head].y + nextx[i][];

                if(nowX<= || nowX> || nowY<= || nowY>)

                    continue;

                if(maps[nowX][nowY] == )

                {

                    maps[nowX][nowY] = ;

                    ques[tail].x = nowX;

                    ques[tail].y = nowY;

                    ques[tail].step = ques[head].step + ;

                    tail++;

                }

                if(nowX == x2 && nowY == y2)

                {

                    goto f1;

                }

            }

            head++;

        }

        f1:printf("To get from %c%d to %c%d takes %d knight moves.\n",ch[],y1,ch[],y2,ques[tail-].step);

    }

    return ;

}

/*

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.

*/