RePorridge

Nothing change but our heart

POJ 2488 A Knight's Journey 题解

A Knight's Journey
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 26210 Accepted: 8950
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



因为题目要求 print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line.即输出字典序最小的一组答案

字典序最小就是按位比较ASCII码,相等的比较下一位,知道不相等的为止或者长度比另一个长 比如 "abc" < "bbc" "abcd" > "abc" 因为要是有路径的话长度都是一样所以不需要考虑路径长度的问题。

直接考虑每个路径,在搜索的时候只要优先往A副1的方向走,这样获得的第一条路径就是字典序最小的路径了。按照图上的路径。有的题解是转过来的,其实只要写程序的时候注意一下就行了。

这个题目我WA了N多次的原因是Scenario自己打的没有复制,然后输错了。太二了

POJ2488.cpp

posted on 2013-09-08 20:31 Porridge 阅读(426) 评论(0)  编辑 收藏 引用 所属分类: POJ题解


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2013年9月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜