KnightTour

SRM 334 · 2007-01-13 · by Andrew_Lazarev

SRM 334 · 2007-01-13 · by Andrew_Lazarev · Simple Math, Simulation

Show categories

Class Name: KnightTour

Return Type: String

Method Name: checkTour

Arg Types: (vector<string>)

Problem Statement

A knight is a chess piece that moves by simultaneously shifting one square along one axis and two squares along the other. A knight's tour of a chessboard is a sequence of moves made by a knight such that each square of the board is visited exactly once. If the final position in the tour is a knight's move away from the first position, the tour is called re-entrant. The picture below shows a re-entrant knight's tour for a 6x6 chessboard.

Josh is trying to find another re-entrant knight's tour on a 6x6 chessboard. He needs a program to make sure he doesn't make any mistakes.

You will be given a String[] cells containing the sequence of cells visited by the knight in order. Each element represents a single cell and is in the form "<letter><digit>" (quotes for clarity), where <letter> is a letter representing the column and <digit> is a digit representing the row. "A1" represents the bottom-left corner of the board, and "F6" represents the top-right corner (see the picture). Return the String "Valid" if cells contains a valid re-entrant knight's tour, and return "Invalid" otherwise (all quotes for clarity).

Constraints

cells will contain exactly 36 elements.
Each element of cells will be in the form "<letter><digit>" (quotes for clarity), where <letter> is an uppercase letter between 'A' and 'F', inclusive, and <digit> is a digit between '1' and '6', inclusive.

Examples

{"A1", "B3", "A5", "C6", "E5", "F3",
 "D2", "F1", "E3", "F5", "D4", "B5",
 "A3", "B1", "C3", "A2", "C1", "E2",
 "F4", "E6", "C5", "A6", "B4", "D5",
 "F6", "E4", "D6", "C4", "B6", "A4",
 "B2", "D1", "F2", "D3", "E1", "C2"}
Returns: "Valid"

The example from the statement.

{"A1", "C2", "E3", "F5", "D4", "B3",
 "A1", "C2", "E3", "F5", "D4", "B3", 
 "A1", "C2", "E3", "F5", "D4", "B3", 
 "A1", "C2", "E3", "F5", "D4", "B3", 
 "A1", "C2", "E3", "F5", "D4", "B3", 
 "A1", "C2", "E3", "F5", "D4", "B3"}
Returns: "Invalid"

Some cells are not visited.

{"D4", "F5", "D6", "B5", "A3", "B1", 
 "D2", "F1", "E3", "D1", "F2", "E4", 
 "F6", "D5", "B6", "A4", "B2", "C4", 
 "A5", "C6", "E5", "F3", "E1", "C2", 
 "A1", "B3", "C5", "E6", "F4", "E2", 
 "C3", "A2", "C1", "D3", "B4", "A6"}
Returns: "Invalid"

This tour is not re-entrant.

{"D4", "F5", "D6", "B5", "A3", "B1", 
 "D2", "F1", "E3", "D1", "F2", "E4", 
 "F6", "D5", "B6", "A4", "B2", "C4", 
 "A5", "C6", "E5", "F3", "E1", "C2", 
 "A1", "B3", "C5", "A6", "B4", "A2", 
 "C3", "E2", "C1", "D3", "F4", "E6"}
Returns: "Valid"

{"E3", "F1", "D2", "B1", "A3", "B5", "D6", "F5", "D4", "C2", "A1", "B3", "A5", "C6", "E5", "F3", "E1", "D3", "B4", "A6", "C5", "E6", "F4", "E2", "C1", "A2", "C3", "D1", "F2", "E4", "F6", "D5", "B6", "A4", "B2", "C4"}
Returns: "Valid"

37)

{"C5", "D3", "F2", "D1", "B2", "A4", 
 "B6", "D5", "C3", "E4", "F6", "B3", 
 "A1", "C2", "E1", "F3", "E5", "C6", 
 "A5", "C4", "A3", "B1", "D2", "F1", 
 "E3", "F5", "D6", "B5", "D4", "E6", 
 "F4", "E2", "C1", "A2", "B4", "A6"}
Returns: "Invalid"

"F6-B3" is not a valid knight move.

Submissions are judged against all 46 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class KnightTour with a public method string checkTour(vector<string> cells) · 46 test cases · 2 s / 256 MB per case