UVa 439/HDU 1372/POJ 2243/ZOJ 1091 Knight Moves(BFS纯数学方法)

2024-03-05 21:08

本文主要是介绍UVa 439/HDU 1372/POJ 2243/ZOJ 1091 Knight Moves(BFS纯数学方法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

439 - Knight Moves

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=380

http://acm.hdu.edu.cn/showproblem.php?pid=1372

http://poj.org/problem?id=2243

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1091

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.

题意:

在辽阔的N*N大草原上(棋盘)上你有一只草泥马,马走日。求从a到b怎么走步数最小。


思路:

1. BFS,复杂度O(N^2),N指棋盘边长。

2. 数学方法,复杂度O(N^2),但系数比第一种小很多:

设横纵坐标的差值分别是x,y。由于我们的草泥马只能有8种走法,实际上只会出现4种(方向向量有(1,2),(2,1),(1,-2),(2,-1),(-1,2),(-2,1),(-1,-2),(-2,-1)8种,但是如果要走最小的次数,就不可能同时出现(1,2)和(-1,-2)这样相反的方向向量,所以只会出现4种)。所以,我们设方向向量为(1,2),(2,1),(2,-1),(1,-2)的有a,b,c,d次,其中a,b,c,d可以为负数(比如a为负数代表方向向量为(-1,-2))。

于是,可以列两个方程:


我们要求的是|a|+|b|+|c|+|d|的最小值。把a,b,看做常量,解得:


所以a+2b≡2x+y(mod 3),即a≡-2b+2x+y(mod 3)(-3≤a,b3)

但由于a,b关系的制约,当b在-3到3范围内变动时,a只有三种情况(取-3,0,3或-2,1或-1,2)

所以a,b的组合有16或17种,比较每种情况的|a|+|b|+|c|+|d|,求最小的即可。

但是在计算角落时要另外考虑,比如(a1,b2)按上面方法算的是2,实际是4。

经过计算知,对于8*8的只有4种情况:(a1,b2),(a8,b7),(g2,h1),(g7,h8),

对这四种情况单独拿出来说就好了。


完整代码:

BFS,很慢。

/*UVaOJ: 0.022s*/
/*HDU: 31ms,244KB*/
/*POJ: 266ms,156KB*/
/*ZOJ: 10ms,180KB*/#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;bool vis[9][9];
int a, b, c, d;
int mov[8][2] = {1, 2, -1, 2, -2, 1, -2, -1, -1, -2, 1, -2, 2, -1, 2, 1};struct node
{int x, y, step;
} lnode;int bfs()
{int i;queue<node>q;node cur, next;cur.x = a;cur.y = b;cur.step = 0;vis[cur.x][cur.y] = true;q.push(cur);while (!q.empty()){cur = q.front();q.pop();for (i = 0; i < 8; i++){next.x = cur.x + mov[i][0];next.y = cur.y + mov[i][1];if (next.x >= 1 && next.x <= 8 && next.y >= 1 && next.y <= 8){if (next.x == c && next.y == d){next.step = cur.step + 1;return next.step;}if (!vis[next.x][next.y]){next.step = cur.step + 1;vis[next.x][next.y] = true;q.push(next);}}}}return -1;
}int main()
{char str[5], str2[5];while (~scanf("%s %s", str, str2)){memset(vis, 0, sizeof(vis));a = str[0] - '`' ;//'a'前面是'`'b = str[1] - '0';c = str2[0] - '`' ;d = str2[1] - '0';int ans = 0;if (a != c || b != d)ans = bfs();printf("To get from %s to %s takes %d knight moves.\n", str, str2, ans);}return 0;
}


数学方法,较快。

/*UVaOJ: 0.019s*/
/*HDU: 15ms,232KB*/
/*POJ: 16ms,144KB*/
/*ZOJ: 0ms,180KB*/#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int main()
{char except[8][3] = {"a1", "b2", "a8", "b7", "g2", "h1", "g7", "h8"};char s1[5], s2[5];int  x, y, a, b, c, d,sum, m, temp;while (~scanf("%s%s", s1, s2)){if (!strcmp(s1, s2)){printf("To get from %s to %s takes 0 knight moves.\n", s1, s2);continue;}bool flag = false;for (int i = 0; i < 8; i += 2)if (!((strcmp(s1, except[i]) || strcmp(s2, except[i + 1]))&& (strcmp(s1, except[i + 1]) || strcmp(s2, except[i])))){flag = true;break;}if (flag){printf("To get from %s to %s takes 4 knight moves.\n", s1, s2);continue;}x = s2[0] - s1[0];y = s2[1] - s1[1];sum = 1 << 6;//下面a,b的取值范围是由-3<=a,b<=3所确定的//注意b取负数和正数的情况是不一样的//注意取模时,-1%3!=2而是=-1for (b = -3; b <= 3; b++){m = (y + 2 * x - 2 * b) % 3;for (a = m - 3; a <= m + 3; a += 3){c = (2 * x + y - 4 * a - 5 * b) / 3;d = (5 * a + 4 * b - x - 2 * y) / 3;temp = abs(a) + abs(b) + abs(c) + abs(d);if (temp < sum)sum = temp;}}printf("To get from %s to %s takes %d knight moves.\n", s1, s2, sum);}return 0;
}


题外话:可以打表。

这篇关于UVa 439/HDU 1372/POJ 2243/ZOJ 1091 Knight Moves(BFS纯数学方法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/777809

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

Windows 上如果忘记了 MySQL 密码 重置密码的两种方法

《Windows上如果忘记了MySQL密码重置密码的两种方法》:本文主要介绍Windows上如果忘记了MySQL密码重置密码的两种方法,本文通过两种方法结合实例代码给大家介绍的非常详细,感... 目录方法 1:以跳过权限验证模式启动 mysql 并重置密码方法 2:使用 my.ini 文件的临时配置在 Wi

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

SQL中redo log 刷⼊磁盘的常见方法

《SQL中redolog刷⼊磁盘的常见方法》本文主要介绍了SQL中redolog刷⼊磁盘的常见方法,将redolog刷入磁盘的方法确保了数据的持久性和一致性,下面就来具体介绍一下,感兴趣的可以了解... 目录Redo Log 刷入磁盘的方法Redo Log 刷入磁盘的过程代码示例(伪代码)在数据库系统中,r

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的