hdu1372 dfs搜索之国际象棋的马

原题地址

题意

一个8x8的国际象棋棋盘，你有一个棋子“马”。算出棋子“马”从某一格到还有一格子的最少步数。

与普通dfs不同的是，你能走的路线不是上下左右，四个方向。

而是由“日”

字组成的8个方向。尽管是国际象棋的马。可是事实上和中国象棋的马走法还是一样的。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int d[8][2]={-1,-2,1,-2,-1,2,1,2,-2,1,-2,-1,2,1,2,-1};

int map[8][8];

int bi,bj;

void dfs(int i,int j,int step)

{

    map[i][j]=step;

    if(bi==i&&bj==j)

        return;

    for(int ii=0;ii<8;ii++)

    {

        int x=i+d[ii][0];

        int y=j+d[ii][1];

        if(x<0||x>=8||y<0||y>=8||map[x][y]<=step+1)

            continue;

        dfs(x,y,step+1);

    }

}

int main()

{

    char a,b;

    int ai,aj;

    while(cin>>a>>aj>>b>>bj)

    {

        memset(map,0x3f,sizeof map);

        ai=a-'a';

        bi=b-'a';

        aj--;

        bj--;

        dfs(ai,aj,0);

        printf("To get from %c%d to %c%d takes %d knight moves.\n",a,aj+1,b,bj+1,map[bi][bj]);

    }

}

题外话

中国象棋和国际象棋应该还是有些渊源的，的确二者的起源不同。

中国象棋在战国曾经就有了，而国际象棋流行的说法是起源于古印度。

二者在千百年的历史长河中，其规则和形态也都是在一直变化的。中国古代非常早就和印度有了往来，所以中国象棋在历史上遇到了国际象棋也是极为有可能的。二者相互影响。然后又各自发展，比方两种象棋的棋盘都是8x8的格子，两种棋中马和象都是一样的走法。

而在古代国际象棋中的皇后的走法没有现在这么厉害，文献曾记载的皇后走法和中国象棋的士是同样的。同样在中国曾出土的唐代的象棋棋盘居然是黑白格子相间的，这无疑与现代的国际象棋棋盘同样。而中国象棋中的楚河汉界是在宋代出现的。