北大 poj 2243 Knight moves

这是我第一次做广搜的题，呃，错了无数次，原因有二：一是因为对广搜的形式理解不好，不知道怎么去记忆路径，第二是忘了原来骑士走的是“日”字形……也就是先向某个方向走2步，再向左或右走一步。所以一共有八个方向……

/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
        URL   : http://poj.org/problem?id=2243
        Name  : Knight Moves
        Date  : Tuesday, April 20, 2010
        Time Stage : 0:14
        Result:
Test Data:
//----------------------------------------------------------------------------*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;
struct node
{
        int x, y;
};
const int directions[8][2] = { {2, 1}, {1, 2}, {2, -1}, {-1, 2},
                               {1, -2}, {-2, 1}, {-1, -2}, {-2, -1} };
char a, b;
int x, y, x2, y2;
int minTrip, tmpTrip;
int mark[10][10];
void out( )
{
        int i, j;
        for( i = 1; i <= 8; i++ )
        {
                for( j = 1; j <= 8; j++ )
                        cout << mark[i][j] << "  ";
                cout << endl;
        }
}
void bfs()
{
        memset( mark, 0, sizeof( mark ) );
        mark[x][y] = 1;
        if( x == x2 && y == y2 )
                return ;
        int i, j, k;
        minTrip = 0x0f0f0f0f;
        tmpTrip = 0;
        node n;
        queue<node> q;
        n.x = x;
        n.y = y;
        q.push( n );
        while( !q.empty() )
        {
                n = q.front();
                q.pop();
                for( i = 0; i < 8; i++ )
                {
                        node nt;
                        nt.x = n.x + directions[i][0];
                        nt.y = n.y + directions[i][1];
                        if( nt.x <= 0 || nt.y <= 0 || nt.x > 8 || nt.y > 8 )
                                continue; // border
                        if( !mark[nt.x][nt.y] )
                        {
                                mark[nt.x][nt.y] = mark[n.x][n.y] + 1;
                                q.push( nt );
                        }
                        if( nt.x == x2 && nt.y == y2 ) // final point
                        {
                                return ;
                        }
                }
        }
}
int main()
{
        int i, j, k, tcase;
        while( cin >> a >> y >> b >> y2 )
        {
                x = a - 'a' + 1;
                x2 = b - 'a' + 1;
                bfs();
                printf("To get from %c%d to %c%d takes %d knight moves./n", a, y, b, y2, mark[x2][y2]-1);
        }
        return 0;
}