文档章节

poj 2488 A Knight's Journey

locusxt
 locusxt
发布于 2013/12/19 22:51
字数 618
阅读 136
收藏 1
poj

dfs 注意字典序输出

A Knight's Journey
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 27075 Accepted: 9231

Description

Background 
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey 
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? 

Problem 
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number. 
If no such path exist, you should output impossible on a single line.

Sample Input

3
1 1
2 3
4 3

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

Source

TUD Programming Contest 2005, Darmstadt, Germany

[Submit]   [Go Back]   [Status]   [Discuss]

/*=============================================================================
#     FileName: 2488.cpp
#         Desc: poj 2488
#       Author: zhuting
#        Email: cnjs.zhuting@gmail.com
#     HomePage: my.oschina.net/locusxt
#      Version: 0.0.1
#    CreatTime: 2013-12-19 22:46:13
#   LastChange: 2013-12-19 22:46:13
#      History: dfs
=============================================================================*/
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#define maxn 66

int x_size = 0, y_size = 0;
int chess_num = 0;/*棋盘的格子数*/
int rout[maxn] = {0};/*路径*/

bool color[10][10] = {0};/*记录是否走过*/
int col_sum = 0;/*走过的点的总数*/


const int del_x[8] = {-2, -2, -1, -1, 1, 1, 2, 2};/*路径要字母序*/
const int del_y[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

bool dfs(int x, int y)
{
	if (x < 0 || x >= x_size || y < 0 || y >= y_size)/*越界*/
		return 0;
	if (color[x][y])/*已经走过*/
		return 0;
	color[x][y] = 1;
	++col_sum;
	rout[col_sum - 1] = x * y_size + y;
	if (col_sum == chess_num)/*已经遍历全部*/
		return 1;
	for (int i = 0; i < 8; ++i)
	{
		bool is_pos = dfs(x + del_x[i], y + del_y[i]);
		if (is_pos) return 1;
	}
	--col_sum;
	color[x][y] = 0;
	return 0;
}

void init()
{
	memset(color, 0, sizeof(color));
	memset(rout, 0, sizeof(rout));
	chess_num = x_size * y_size;
	col_sum = 0;
}

int main()
{
	int test_num = 0;
	scanf("%d", &test_num);
	for (int i = 0; i < test_num; ++i)
	{
		printf("Scenario #%d:\n", i + 1);
		scanf("%d %d", &y_size, &x_size);/*写完发现搞反了*/
		init();
		if (dfs(0, 0))
		{
			for (int j = 0 ; j < chess_num; ++j)
			{
				printf("%c%d", rout[j] / y_size + 'A', rout[j] % y_size + 1);
			}
			printf("\n\n");
			continue;
		}
		printf("impossible\n\n");
	}
	return 0;
}




© 著作权归作者所有

locusxt
粉丝 27
博文 140
码字总数 90989
作品 0
海淀
程序员
私信 提问
POJ 2488 A Knight's Journey 【dfs + 思维】

传送门 // 题意: 给定一个n*m的棋盘, 问是否有一种方式可以使这匹马走遍这个棋盘的每一个点, 有的话打印出路径, 并且字典序要尽可能的小. 思路: 可能难点的地方就是字典序那, 其实不用管,...

anxdada
2018/02/26
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
Linux学习记录--匿名管道通信

匿名管道通讯 管道是Linux支持的最初Unix IPC形式之一,具有以下特点: 1.管道是半双工的,数据只能向一个方向流动;需要双方通信时,需要建立起两个管道; 2.只能用于父子进程或者兄弟进程之...

tiankefeng0520
2014/04/23
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
160
1
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

没有更多内容

加载失败,请刷新页面

加载更多

如何使用soapUI模拟webservice客户端发送请求

参考资料 https://jingyan.baidu.com/article/cbcede0712849a02f40b4d88.html 左边是请求参数,可以自己填写!按着那个绿色三角箭头可以模拟发送请求,右边是返回的报文 soapui如何发送xml格...

故久呵呵
17分钟前
3
0
Java Security 介绍

1.介绍 Java平台设计的重点是安全性。在其核心,java语言本身是类型安全的并且提供了垃圾自动回收,这使其增加了应用程序代码的健壮性。安全的类加载以及验证机制确保了只有合法的代码才能够...

lixiaobao
23分钟前
3
0
Niushop开源商城系统-分销商管理

分销商管理 1.分销员的招募与管理 如何申请成为分销员? 在wap端个人中心满足之前设置的升级条件,可以申请分销员 开启分销商审核,需要在后台分销商管理——》待审核处进行审核通过。 通过完...

niushop-芳
24分钟前
2
0
为什么大公司一定要使用 DevOps?

究竟什么是DevOps? 要想回答这个问题,首先要明确DevOps这个过程参与的人员是谁,即开发团队和IT运维团队。那么,DevOps的意图是什么呢?即在两个团队之间,建立良好的沟通和协作,更快更可靠...

cs平台
26分钟前
4
0
高危预警|RDP漏洞或引发大规模蠕虫爆发,用户可用阿里云免费检测服务自检,建议尽快修复

2019年9月6日,阿里云应急响应中心监测到Metasploit-framework官方在GitHub空间公开了针对Windows远程桌面服务远程命令执行漏洞(CVE-2019-0708)的利用代码。利用该代码,无需用户交互操作,即...

Mr_zebra
31分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部