COMCB - Complete Chess Boards
BuggyD has always been fascinated with chess boards (though he really sucks at chess). He makes an observation that a chess board is complete with respect to knights and rooks and incomplete with respect to bishops (unless the dimensions are 1 × 1). A complete chess board is one in which it is possible to traverse all the squares starting from one possible square. Knights have always been his favourite pieces and he has decided to analyze completeness with respect to knights. Given the dimesions of the chess board help BuggyD find the lexicographically first path that visits all squares of a chess board with a knight.
Each square must be traversed only once. Note that a knight can only move two squares in one direction and one square perpendicular to the previous direction.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of a single line cotaining two integers (X and Y) separated by a single space, specifying the dimensions of the chess board. The numbers 1 to X denote rows and the capital letters A to Y denote the coloumns. Each square is represented by its column index followed by it's row index - for example, B4 denotes the square in the 4th row and 2nd column.
The total number of squares on the chess board will be no more than 26.
Output
For each test case output one line consisting of the lexicographically first path of the knight, or "-1" (quotes for clarity) if the chess board is incomplete with respect to a knight.
Example
Input: 1 4 5 Output: A1B3C1A2B4D3E1C2D4E2C3A4B2D1E3C4A3B1D2E4
hide comments
nadstratosfer:
2019-12-17 11:49:44
Didn't expect to use the approach that I previously only read about, would have skipped the problem assuming I didn't have the skillz! My initial ideas led nowhere though and adapting them to the situation, I've invented an algorithm others pick up at school. Waste of time for some I guess, awesome experience for me. Highly recommended problem for other self-trained coders! |
|
Luv Karakoti:
2014-07-21 22:26:14
I am not able to comprehend the meaning of the phrase 'first lexicographical' path. Can please someone clarify this?
|
|
Krunal:
2011-03-04 00:37:56
What if input is given as:
|
|
Krunal:
2011-03-04 00:18:07
One Help: It is "Lexicographic order"
|
Added by: | Matthew Reeder |
Date: | 2006-10-29 |
Time limit: | 1s |
Source limit: | 30000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Al-Khawarizm 2006 |