首页 > 代码库 > hdu1372 dfs搜索之国际象棋的马
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的格子,两种棋中马和象都是一样的走法。而在古代国际象棋中的皇后的走法没有如今这么厉害,文献曾记载的皇后走法和中国象棋的士是相同的。同样在中国曾出土的唐代的象棋棋盘竟然是黑白格子相间的,这无疑与现代的国际象棋棋盘相同。而中国象棋中的楚河汉界是在宋代出现的。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。