TopCoder problem "DukeOnChessBoard" used in SRM 375 (Division II Level Two)



Problem Statement

    

Let's define a duke as a chess figure that is only allowed to move 1 cell up, down, left or right.

A duke is placed on an n×n board in the cell initPosition. In this problem, columns are marked 'a', 'b', etc. from left to right, and rows are marked '1', '2', etc. from bottom to top. Cells are notated as "cr" (quotes for clarity), where c is the column and r is the row.

Let's describe a duke's path as a dash-separated list of cells visited by the duke. For example, "c5-b5-b4" is a path consisting of two moves. The first move is one cell to the left (from c5 to b5), and the second is one cell down (from b5 to b4).

A path is called simple if it contains no repeated cells.

Return the lexicographically greatest simple path of a duke starting in initPosition. If the length of the path exceeds 40 characters, return only the first 20 and the last 20 characters, separated by three dots. (See Example #1).

 

Definition

    
Class:DukeOnChessBoard
Method:dukePath
Parameters:int, String
Returns:String
Method signature:String dukePath(int n, String initPosition)
(be sure your method is public)
    
 

Notes

-A String A is greater than a String B lexicographically if B is a proper prefix of A, or if A has a greater character at the first position where the strings differ.
 

Constraints

-n will be between 2 and 8, inclusive.
-initPosition will contain exactly 2 characters.
-The first character of initPosition will be a lowercase letter between 'a' and 'h', inclusive.
-The second character of initPosition will be a digit between '1' and '8', inclusive.
-initPosition will denote a cell inside the n×n board.
 

Examples

0)
    
3
"b2"
Returns: "b2-c2-c3-b3-a3-a2-a1-b1-c1"
After the first move to the right, the duke will traverse the perimeter of the board in the counterclockwise direction.
1)
    
4
"d4"
Returns: "d4-d3-d2-d1-c1-c2-c3...b3-b2-b1-a1-a2-a3-a4"
The duke will move down three times, then left, then up three times and left, in a snake-like fashion. The lexicographically greatest path is 47 characters long, so its middle part is replaced by "...".
2)
    
3
"a2"
Returns: "a2-b2-c2-c3-b3-a3"
3)
    
4
"d3"
Returns: "d3-d4-c4-c3-c2-d2-d1...b2-b3-b4-a4-a3-a2-a1"
4)
    
8
"a8"
Returns: "a8-b8-c8-d8-e8-f8-g8...a1-a2-a3-a4-a5-a6-a7"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8268

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10794&pm=8268

Writer:

darnley

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Greedy, Search