Connection Status:
Competition Arena > PawnsAndKings

PawnsAndKings

TCO09 Round 5 · 2009-02-24 · by boba5551

TCO09 Round 5 · 2009-02-24 · by boba5551 · Dynamic Programming
Class Name: PawnsAndKings
Return Type: int
Method Name: minNumberOfMoves
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a String[] board representing a standard 8x8 chess board. The '.' character represents an empty cell, 'P' represents a cell occupied by a pawn, and 'K' represents a cell occupied by a king.

In a single move, a king can move to any of its 8 neighboring cells. If you move a king into a cell occupied by a pawn, the king will capture that pawn. You can never move a king outside the board or into a cell already occupied by another king.

Return the minimal number of moves required for the kings to capture all the pawns.

Constraints

  • board will contain exactly 8 elements.
  • Each element of board will contain exactly 8 characters.
  • Each character of each element of board will be '.', or an uppercase 'P', or an uppercase 'K'.
  • The number of 'P' characters will be between 1 and 10, inclusive.
  • The number of 'K' characters will be between 1 and 10, inclusive.
Examples
0)
{".PPPPKP.", 
 "........", 
 "........", 
 "........", 
 "........", 
 "........", 
 "........", 
 "........"}
Returns: 6

The only king will make the minimal number of moves by first capturing the only pawn at its right side and then capturing the other pawns.

1)
{"P......P", 
 "........", 
 "........",
 "........",
 "...KK...",
 "........",
 "........",
 "P......P"}
Returns: 20

If we mark the kings with A and B and the pawns with 1, 2, 3 and 4, then one possible solution is that A captures the pawns 1 and 2, and B captures the pawns 3 and 4. 1......4 ........ ........ ........ ...AB... ........ ........ 2......3

2)
{"PK....KP", "K......K", "........", "........", "...KK...", "........", "K......K", "PK....KP"}
Returns: 4
3)
{"........", "..P.KK..", ".P..KPK.", "..P.K...", "K...K.PK", ".P..P...", ".K...P.K", "..P...P."}
Returns: 11
4)
{".PP.K..P", "..P.KK..", ".P..KPK.", "..P.K...", "K.....P.", ".P......", ".K...P..", "...KK..."}
Returns: 13

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

Coding Area

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

Submitting as anonymous