• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

【题解】KnightMoves-C++

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目
Description
在一个8*8的棋盘上,一只中国象棋中的马要从一个点跳到另一个点。问最少需要多少步。
Input
整个测试组由多组数据组成,请做到文件底结束。
对于每组数据,前两个坐标代表出发点,后两个代表结束点。注意坐标第一位为a至h中某个字母,第二位为1到8某个数字。
Output
对于每个测试请输出"To get from xx to yy takes n knight moves.".
Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

思路
广搜,每次输入字符串先存起来,转成两对坐标,按照正常的搜索去做就行了,然后唯一不同的是dir数组要按照马的走法来打,具体看下面代码是怎么写的,其他的坑点不多,就是要注意输出格式中空格的位置以及个数(真心劝告!!!)

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string o1,o2;
 4 int sx,sy,ex,ey,cnt;
 5 int dir[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
 6 struct node
 7 {
 8     int x,y,t;
 9     node(){};
10     node(int xx,int yy,int tt)
11     {
12         x=xx,y=yy,t=tt;
13     }
14 };
15 bool vis[10][10];
16 bool in(int x,int y)
17 {
18     return 1<=x&&x<=8&&1<=y&&y<=8;
19 }
20 void bfs()
21 {
22     queue<node> q;
23     q.push(node(sx,sy,0));
24     vis[sx][sy]=0;
25     while(!q.empty())
26     {
27         node now=q.front();
28         q.pop();
29         if(now.x==ex&&now.y==ey)
30         {
31             cout<<"To get from "<<o1<<" to "<<o2<<" takes "<<now.t<<" knight moves."<<endl;
32             return;
33         }
34         for(int i=0;i<8;i++)
35         {
36             int tx=now.x+dir[i][0],ty=now.y+dir[i][1];
37             if(in(tx,ty)&&!vis[tx][ty])
38             {
39                 q.push(node(tx,ty,now.t+1));
40                 vis[tx][ty]=1;
41             }
42         }
43     }
44     cout<<"f**k"<<endl;
45     return;
46 }
47 int main()
48 {
49     while(cin>>o1>>o2)
50     {
51         memset(vis,0,sizeof(vis));
52         sx=o1[0]-'a'+1,sy=o1[1]-'0';
53         ex=o2[0]-'a'+1,ey=o2[1]-'0';
54         bfs();
55     }
56     return 0;
57 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
win8下在microsoftvisualstudio2012利用ODP.NET连接ORACLE12c发布时间:2022-07-14
下一篇:
c#客显发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap