文档章节

poj 1915 Knight Moves

locusxt
 locusxt
发布于 2014/11/29 13:42
字数 506
阅读 30
收藏 0
Knight Moves
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 22220 Accepted: 10384

Description

Background 
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him? 
The Problem 
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov. 
For people not familiar with chess, the possible knight moves are shown in Figure 1. 

Input

The input begins with the number n of scenarios on a single line by itself. 
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

Output

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

Sample Input

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

Sample Output

5
28
0

Source

TUD Programming Contest 2001, Darmstadt, Germany

bfs用sdl的list写,效率堪忧。换成queue。
麻烦的是queue没有clear,只能一个一个pop,或者新开一个queue。

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 303

int size = 0;
bool visit[MAXN][MAXN] = {0};

int mx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int my[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int step_num = 0;

struct point
{
	int x;
	int y;
	int n;
};

queue <point> myq;
point sp;
point dp;

void init()
{
	memset (visit, 0, sizeof(visit));
	while(!myq.empty())
	{
		myq.pop();
	}
	return;
}

bool bfs(point p)
{
	int x = p.x;
	int y = p.y;
	int n = p.n;

	if (x < 0 || x >= size || y < 0 || y >= size)
		return false;

	if (visit[x][y])
		return false;
	visit[x][y] = true;

	if (x == dp.x && y == dp.y){
		step_num = n;
		return true;
	}

	for (int i = 0; i < 8; ++i)
	{
		point newp;
		newp.x = x + mx[i];
		newp.y = y + my[i];
		newp.n = n + 1;
		myq.push(newp);
		//printf("%d %d %d\n", newp.x, newp.y, newp.n);
	}
	return false;
}

int main()
{
	int n = 0;

	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &size);
		scanf("%d%d%d%d", &sp.x, &sp.y, &dp.x, &dp.y);
		
		init();
		myq.push(sp);
		while(!myq.empty())
		{
			if(bfs(myq.front()))
				break;
			myq.pop();
		}
		printf("%d\n", step_num);
	}



}



© 著作权归作者所有

locusxt
粉丝 27
博文 140
码字总数 90989
作品 0
海淀
程序员
私信 提问
poj 2488 A Knight's Journey

dfs 注意字典序输出 1 12 34 3 Sample Output Scenario #1:A1 Scenario #2:impossible Scenario #3:A1B3C1A2B4C2A3B1C3A4B2C4 Source [Submit] [Go Back] [Status] [Discuss] /*============......

locusxt
2013/12/19
136
0
acm题目及我的程序(2)——Knight Moves (骑士跳跃)

acm题目,来源 http://acm.zju.edu.cn/show_problem.php?pid=1091 problem statement A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find th......

晨曦之光
2012/03/09
1K
0
棋盘游戏走完k步还能留在棋盘上的概率

Knight Probability in Chessboard 问题: On an x chessboard, a knight starts at the -th row and -th column and attempts to make exactly moves. The rows and columns are 0 indexed......

叶枫啦啦
2018/01/15
40
0
Java How to Program习题_第七章_数组及动态数组(Array and ArrayList)——第一部分(7.1 - 7.22)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/hpdlzu80100/article/details/85386298 这一章的习题非常多,而且都有一定的难度(如海龟绘图、骑士游历等)。...

预见未来to50
2018/12/30
0
0
POJ 3434 Terrarium:题目解答源码

POJ 3434 Terrarium:题目解答源码 A zoology research lab has a terrarium with rare species of snakes.Terrarium is a flat box filled with soil,and has a glass top allowing to watc......

爱mili
2016/09/26
15
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
10
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部