[POJ 2243] Knight Moves【A*】

  • 2018-01-02
  • 0
  • 0

Problem:

Time Limit: 1000MS Memory Limit: 65536K

Description

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

The input 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

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.

Source

Ulm Local 1996

Solution:

本题可以用 A* 搜索水过

关于 A* 算法 (A-star Algorithm) 请看:【转载】A*算法入门

理论上 A* 的估价函数 h() 一定要小于等于当前状态到目标状态的实际代价,才能保证找到最优解

所以 h() 应选取从当前点到目标点的欧几里得距离[1]而不是许多题解里所写的曼哈顿距离[2]数据太水以至于写成曼哈顿距离都可以 AC)。

其中为避免实数运算,代价放大 100 倍处理。

注释:

  1. 欧几里得距离:Euclid(u, v) = sqrt((u.x - v.x)2 + (u.y - v.y)2)。
  2. 曼哈顿距离:Manhattan(u, v) = |u.x - v.x| + |u.y - v.y|。

注意事项:

cmath 中的 sqrt() 参数可以是 float, double, long double。如果写成以下形式:

sqrt(1)

让编译器自动将 int 转换为实型作为参数,在 Windows 下不会报错,但在 Linux 下会返回以下错误:

Compile Error
Main.cpp
%BinDir0%\Main.cpp(33) : error C2668: 'sqrt' : ambiguous call to overloaded function
        math.h(581): could be 'long double sqrt(long double)'
        math.h(533): or       'float sqrt(float)'
        math.h(128): or       'double sqrt(double)'
        while trying to match the argument list '(int)'

必须改写成以下形式才能通过编译:

sqrt(1.0)

Code: O(玄学) [220K, 94MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int dx[8] = { 1, 2, 2, 1,-1,-2,-2,-1};
const int dy[8] = { 2, 1,-1,-2,-2,-1, 1, 2};

char sbuf[5], tbuf[5];

struct State{
	int x, y, step;
	int f, g, h;
	
	inline bool operator < (const State &s2) const {return f > s2.f;}
	
	inline bool isLegal() {return x > 0 && x <= 8 && y > 0 && y <= 8;}
	
	inline void readBuf(const char *buf) {x = buf[0] - 96, y = buf[1] - 48;}
	
	inline void writeScr() {printf("%c%c", x + 96, y + 48);}
} s, t;

priority_queue<State> openList;
bool closeList[10][10];

inline void clearPQ(priority_queue<State> &pq) {priority_queue<State> tmp; swap(tmp, pq);}

#define sqr(x) ((x) * (x))
inline int Euclid(const State &sta) {return (int) sqrt(10000.0 * (sqr(sta.x - t.x) + sqr(sta.y - t.y)));}  // The argument must not be ambiguous !!!

inline int Astar(){
	s.step = 0, s.g = 0, s.h = Euclid(s), s.f = s.g + s.h;
	openList.push(s);
	while(!openList.empty()){
		State u = openList.top(), v;
		openList.pop(), closeList[u.x][u.y] = 1;
		if(u.x == t.x && u.y == t.y) return u.step;
		for(register int i = 0; i < 8; i++){
			v.x = u.x + dx[i], v.y = u.y + dy[i];
			if(!v.isLegal() || closeList[v.x][v.y]) continue;
			v.step = u.step + 1, v.g = u.g + 224, v.h = Euclid(v), v.f = v.g + v.h;  // 100 * sqrt(5) = 224
			openList.push(v);
		}
	}
	return -1;
}

int main(){
	while(scanf("%s", sbuf) != EOF){
		s.readBuf(sbuf);
		scanf("%s", tbuf), t.readBuf(tbuf);
		clearPQ(openList), memset(closeList, 0, sizeof(closeList));
		int ans = Astar();
		printf("To get from %s to %s takes %d knight moves.\n", sbuf, tbuf, ans);
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai