热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

ZOJ1091KnightMoves(BFS)

KnightMoves

Knight Moves



A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.



Input Specification

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output Specification

For each test case, print one line saying "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.

1 //Problem Name: Knight Moves
2 //Source: ZOJ 1091
3 //Author: jinjin18
4 //Main idea:BFS
5 //Language: C++
6 //Point: init;deal with level in BFS--tail;input--gets rather than scanf;
7 //-upline input--sscanf;BFS model;
8 //======================================================================
9
10 #include stdio.h
11 #define MAXSIZE 100000
12 #define INF 10000000
13
14 typedef struct node{
15 char x;
16 int y;
17 }Point;
18 int visited[9][9];
19 void init(){ //初始化,需要二重循环,可用memset函数
20 for(int i = 0; i i++){
21 for(int j = 0; j j++){
22 visited[i][j] = 0;
23 }
24 }
25 }
26 int BFS(char ax,int ay,char bx,int by){
27 int res = 0;
28 int tail = 1;
29 visited[ax-'a'+1][ay] = 1;
30 Point Q[MAXSIZE] = {0};
31 int pre = 0;
32 int last = 1;
33 Q[0].x = ax;
34 Q[0].y = ay;
35 while(pre last){
36 //printf("OK");
37 char thisx = Q[pre].x;
38 int thisy = Q[pre].y;
39 pre++;
40 //printf("%d %c %d\n",res,thisx,thisy);
41 if(thisx == bx thisy == by){ //结束循环
42 return res;
43 }
44 if(thisx + 2 = 'h' thisy + 1 = 8 visited[thisx+2-'a'+1][thisy+1]==0){
45 visited[thisx+2-'a'+1][thisy+1]=1;
46 Q[last].x = thisx+2;
47 Q[last].y = thisy+1;
48 last++;
49 }
50 if(thisx + 2 = 'h' thisy - 1 = 1 visited[thisx+2-'a'+1][thisy-1]==0){
51 visited[thisx+2-'a'+1][thisy-1]=1;
52 Q[last].x = thisx+2;
53 Q[last].y = thisy-1;
54 last++;
55 }
56 if(thisx + 1 = 'h' thisy + 2 = 8 visited[thisx+1-'a'+1][thisy+2]==0){
57 visited[thisx+1-'a'+1][thisy+2]=1;
58 Q[last].x = thisx+1;
59 Q[last].y = thisy+2;
60 last++;
61 }
62 if(thisx + 1 = 'h' thisy - 2 = 1 visited[thisx+1-'a'+1][thisy-2]==0){
63 visited[thisx+1-'a'+1][thisy-2]=1;
64 Q[last].x = thisx+1;
65 Q[last].y = thisy-2;
66 last++;
67 }
68 if(thisx - 2 = 'a' thisy - 1 = 1 visited[thisx-2-'a'+1][thisy-1]==0){
69 visited[thisx-2-'a'+1][thisy-1]=1;
70 Q[last].x = thisx-2;
71 Q[last].y = thisy-1;
72 last++;
73 }
74 if(thisx - 2 = 'a' thisy + 1 = 8 visited[thisx-2-'a'+1][thisy+1]==0){
75 visited[thisx-2-'a'+1][thisy+1]=1;
76 Q[last].x = thisx-2;
77 Q[last].y = thisy+1;
78 last++;
79 }
80
81 if(thisx - 1 = 'a' thisy - 2 =1 visited[thisx-1-'a'+1][thisy-2]==0){
82 visited[thisx-1-'a'+1][thisy-2]=1;
83 Q[last].x = thisx-1;
84 Q[last].y = thisy-2;
85 last++;
86 }
87 if(thisx - 1 = 'a' thisy + 2 = 8 visited[thisx-1-'a'+1][thisy+2]==0){
88 visited[thisx-1-'a'+1][thisy+2]=1;
89 Q[last].x = thisx-1;
90 Q[last].y = thisy+2;
91 last++;
92 }
93 if(tail == pre){ //更新tail
94 tail = last;
95 res++;
96 }
97
98 }
99 return INF;
100
101 }
102
103 int main(){
104 int ay,by;
105 char ax,bx;
106 char S[10];
107 while(gets(S)){ //%s与%c不能用,思考为何?
108 sscanf(S,"%c%d %c%d", ax, ay, bx, by);
109 init();
110 int res = BFS(ax,ay,bx,by);
111 printf("To get from %c%d to %c%d takes %d knight moves.\n",ax,ay,bx,by,res);
112 }
113 return 0;
114
115 }

看到一篇写的比较好的博文:


   



推荐阅读
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法,提供了多个代码示例及应用场景,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 本文深入探讨了 Java 中的 Serializable 接口,解释了其实现机制、用途及注意事项,帮助开发者更好地理解和使用序列化功能。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • 在前两篇文章中,我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象,分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor,即用于描述 Action 方法参数的对象,并详细介绍其工作原理。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]
author-avatar
拍友2602939213
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有