UVa 439

题意

8*8国际象棋, 骑士有八个移动方向, 求最短需要走几步

思路

BFS模版
方向根据实际情况调整一下即可

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int k[10][10], vis[10][10], pre[300];
int turn[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
int x1, y1, x2, y2;

struct POINT
{
    int x, y;
}que[300];

int cnt;

void cntpls( int a ){
    int t = pre[a];
    if( t != 0 )
        cntpls(t);
    cnt++;
}

void Print( int n )
{
    cntpls(n);
    printf("To get from %c%d to %c%d takes %d knight moves.
",y1+'a',8-x1,y2+'a',8-x2,cnt);
}

bool go( int x, int y )
{
    if( x >= 0 && x < 8 && y >= 0 && y < 8 )
        return true;
    return false;
}

void BFS()
{
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    int head = 0, tile = 1, a, b, xx, yy;
    que[0].x = x1;
    que[0].y = y1;
    pre[0] = -1;
    while( head < tile ){
        a = que[head].x;
        b = que[head].y;
        if( a == x2 && b == y2 ){
            Print(head);
            return;
        }
        for( int i = 0; i < 8; i++ ){
            xx = a + turn[i][0];
            yy = b + turn[i][1];
            if( !vis[xx][yy] && go(xx, yy) ){
                //cout << xx << " " << yy << endl;
                vis[xx][yy] = 1;
                que[tile].x = xx;
                que[tile].y = yy;
                pre[tile] = head;
                tile++;
            }
        }
        head++;
    }
    return;
}



int main()
{
    char s[5];
    while( gets(s) != NULL )
    {
        x1 = 8 - ( s[1] - '0' );
        y1 = s[0] - 'a';
        x2 = 8 - ( s[4] - '0' );
        y2 = s[3] - 'a';
        if( x1 == x2 && y1 == y2 )
            printf("To get from %c%d to %c%d takes 0 knight moves.
",y1+'a',8-x1,y2+'a',8-x2);
        else
            BFS();
    }
    return 0;
}