GameOfEight

TC China 08 - 1E · 2008-11-23 · by mateuszek

TC China 08 - 1E · 2008-11-23 · by mateuszek · Graph Theory, Simple Search, Iteration

Show categories

Class Name: GameOfEight

Return Type: int

Method Name: fewestMoves

Arg Types: (vector<string>)

Problem Statement

In "The Game of Eight", you are given a 3x3 board containing 8 squares labelled 1 through 8, and one empty space. The initial state of the board is given in the String[] board, where '.' represents the empty space. In each turn, you pick any square which is horizontally or vertically adjacent to an empty space and move it to the empty space (see example 0 for clarification). Your goal is to arrange the squares so the board looks like this:

{"123",
 "456",
 "78."}

Return the minimum number of moves necessary to achieve this goal, or -1 if it's impossible.

Constraints

board will contain exactly 3 elements.
Each element of board will contain exactly 3 characters.
Each character of each element of board will be a digit ('1' - '8') or a dot ('.').
Each number between 1 and 8 will appear exactly once on the board.

Examples

{"123",
 "485",
 "76."}
Returns: 4

The optimal solution is the following: 123 123 123 123 123 485 --> 485 --> 4.5 --> 45. --> 456 76. 7.6 786 786 78.

{"518", "423", ".76"}
Returns: 18

{"123", "456", "87."}
Returns: -1

{"123",
 "456",
 "78."}
Returns: 0

The game is already completed.

{".23",
 "456",
 "781"}
Returns: -1

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

Coding Area

Language: C++17 · define a public class GameOfEight with a public method int fewestMoves(vector<string> board) · 87 test cases · 2 s / 256 MB per case