MyException - 我的异常网
当前位置:我的异常网» 综合 » hdu1372 dfs搜寻之国际象棋的马

hdu1372 dfs搜寻之国际象棋的马

www.MyException.Cn  网友分享于:2014-07-06  浏览:0次
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的格子,两种棋中马和象都是一样的走法。而在古代国际象棋中的皇后的走法没有如今这么厉害,文献曾记载的皇后走法和中国象棋的士是相同的。同样在中国曾出土的唐代的象棋棋盘竟然是黑白格子相间的,这无疑与现代的国际象棋棋盘相同。而中国象棋中的楚河汉界是在宋代出现的。

文章评论

Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
那些争议最大的编程观点
那些争议最大的编程观点
程序员应该关注的一些事儿
程序员应该关注的一些事儿
我是如何打败拖延症的
我是如何打败拖延症的
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
为什么程序员都是夜猫子
为什么程序员都是夜猫子
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
一个程序员的时间管理
一个程序员的时间管理
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
程序员必看的十大电影
程序员必看的十大电影
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Java程序员必看电影
Java程序员必看电影
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
总结2014中国互联网十大段子
总结2014中国互联网十大段子
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
 程序员的样子
程序员的样子
程序员的鄙视链
程序员的鄙视链
我的丈夫是个程序员
我的丈夫是个程序员
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
旅行,写作,编程
旅行,写作,编程
中美印日四国程序员比较
中美印日四国程序员比较
每天工作4小时的程序员
每天工作4小时的程序员
如何成为一名黑客
如何成为一名黑客
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老程序员的下场
老程序员的下场
代码女神横空出世
代码女神横空出世
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
漫画:程序员的工作
漫画:程序员的工作
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
编程语言是女人
编程语言是女人
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员和编码员之间的区别
程序员和编码员之间的区别
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有