Statistics

Problem Statement for "PawnsAndKings"

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.

Definition

Class:
PawnsAndKings
Method:
minNumberOfMoves
Parameters:
String[]
Returns:
int
Method signature:
int minNumberOfMoves(String[] board)
(be sure your method is public)

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

  1. {".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.

  2. {"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

  3. {"PK....KP", "K......K", "........", "........", "...KK...", "........", "K......K", "PK....KP"}

    Returns: 4

  4. {"........", "..P.KK..", ".P..KPK.", "..P.K...", "K...K.PK", ".P..P...", ".K...P.K", "..P...P."}

    Returns: 11

  5. {".PP.K..P", "..P.KK..", ".P..KPK.", "..P.K...", "K.....P.", ".P......", ".K...P..", "...KK..."}

    Returns: 13

  6. {".P....K.", "K.PK..P.", "K.K.....", "KP......", "...P...K", "......P.", "........", ".K.PP..."}

    Returns: 10

  7. {"....K...", ".......P", "........", "K.K.....", "....P...", "...K....", ".....K..", "..K..K.."}

    Returns: 4

  8. {".P.P....", "K...PPK.", "........", ".....P.P", "...P.P..", ".....K..", "....K...", ".P...P.."}

    Returns: 15

  9. {"........", ".......P", "........", "K..P.P.K", ".K....K.", "........", "....P...", ".....P.."}

    Returns: 9

  10. {"........", ".P......", "........", "....P..K", ".....K.P", "........", ".K......", "......P."}

    Returns: 8

  11. {"P.P..K..", ".......K", "P.P..KK.", "....PP..", "......P.", "...P.P..", "....P...", "...K...."}

    Returns: 14

  12. {".P......", "........", ".......K", "....K...", "........", "P.P...P.", "..K.....", "......K."}

    Returns: 8

  13. {"K..P...P", "......P.", "PP......", ".......K", ".K......", ".P..KK.P", "KP...P..", "......P."}

    Returns: 14

  14. {"K......K", "........", "K....P..", "......P.", "......P.", "P..P.P.P", "....P..K", "..PK.P.."}

    Returns: 13

  15. {"....K...", "..K.....", ".....KKK", "....K..P", "........", ".K......", "........", "......K."}

    Returns: 1

  16. {"...P....", "..P...P.", "........", "......P.", "....PP..", "....K...", ".P......", ".....K.."}

    Returns: 13

  17. {"P.K.....", "....P...", "........", "......K.", "........", ".......K", "........", "...P...."}

    Returns: 8

  18. {".P...P..", "PK.P....", "K......K", "........", "........", "..P.....", "K....P..", ".K....P."}

    Returns: 12

  19. {"........", "P..K....", ".......K", "P....K..", "...PP...", "K.K...PK", "....P...", ".K.....P"}

    Returns: 11

  20. {"........", "P..K....", "........", "P.......", "...P....", "........", ".....K..", "K......."}

    Returns: 7

  21. {"..P.....", "........", ".P......", "P.......", "........", "..P..KP.", "....P...", "........"}

    Returns: 10

  22. {"P.KK.K..", "...P.P.P", "........", "......K.", ".K..P...", "...P..P.", ".PP.....", "........"}

    Returns: 13

  23. {".....P.P", "..K....P", "....K...", "..PP...P", "...K..KK", "........", "K.......", "KP.K...."}

    Returns: 9

  24. {"K..P....", ".....P..", ".......P", "........", "........", "........", "........", ".P......"}

    Returns: 13

  25. {"........", "P.......", "........", "........", "........", "..P.....", "....K...", "....P..."}

    Returns: 7

  26. {"P..P.K..", "K......P", "....K...", "PPK.KK..", "...K....", "P......K", "..K.P.PK", "...P.P.."}

    Returns: 13

  27. {"K...P...", "KK.PPP.P", "K.K.....", "..KK....", "K.P.....", "........", "KPK.....", "..PPP..."}

    Returns: 11

  28. {"P.....K.", ".P...P..", "......P.", "PPK..K..", "K.P..K..", ".PK.....", "KPP...K.", ".K...K.."}

    Returns: 11

  29. {".P......", "..P..P.K", "...P...K", "....PKK.", "P....K.K", "..P....K", ".....KP.", "...PPKK."}

    Returns: 13

  30. {"....K..P", ".K.P..KP", "PK..K..K", "P....P..", "...KK...", "..K.....", "..K.....", "PPP...P."}

    Returns: 12

  31. {"PK...KPK", "......K.", "...K....", "..KPK...", "...K....", "........", "........", "K..P.K.P"}

    Returns: 8

  32. {"P.P.P.P.", ".K.K.K.K", "........", "P.....P.", "..K..K..", "........", "P.P.P.P.", ".K.K.K.K"}

    Returns: 11

  33. {"K.K..K.K", "........", "K.......", "....P...", "...P....", "K.......", "........", "K.K..K.K"}

    Returns: 4

  34. {"KKKKKKKK", "...KK...", "........", "........", "........", "........", "...PP...", "PPPPPPPP"}

    Returns: 15

  35. {"K......P", ".K....P.", "..K..P..", "...KP...", "...PK...", "..P..K..", ".P....K.", "P.PKPK.K"}

    Returns: 10

  36. {"..K....K", "P...K...", "K......P", ".P......", "..P..K..", "P...PPKK", ".P.P.KP.", ".K...K.."}

    Returns: 12

  37. {"..P..K.K", "K.P.P.P.", ".......P", "..K.K...", "PK.KP...", "PP.KK...", "......K.", "..P....."}

    Returns: 12

  38. {"........", "..P.K...", ".KP..K..", "K....K..", "P....PKP", ".PPKPKK.", "........", "..PK...P"}

    Returns: 11

  39. {"..P...K.", "...P....", "..K.K...", "......K.", "PPP..PP.", "..KK....", "P.KK.PKK", "..P....."}

    Returns: 11

  40. {"...K....", "KP.P....", ".PPPP..K", "PKPK..K.", ".P......", "..K.....", "...KK..K", "..P....."}

    Returns: 10

  41. {"........", ".P..P...", ".K..P...", "........", "........", ".....K..", ".K......", "........"}

    Returns: 5

  42. {"..K.PK..", "K.K.K...", ".K..K...", "........", ".....P..", "........", "........", "........"}

    Returns: 3

  43. {"...P..K.", ".K..PP..", ".P....P.", "...P....", "..PKKPK.", "P...K...", "....KK.K", "....P..."}

    Returns: 12

  44. {"......KK", "........", ".K....K.", "......P.", "...P...P", "......K.", "..K..P.K", "P.....P."}

    Returns: 8

  45. {".......K", ".K.P....", "K..K....", "......K.", "........", ".....P..", "........", "P.....KK"}

    Returns: 8

  46. {"P......P", "........", "........", "........", "....K...", "........", "........", "P......P"}

    Returns: 24

  47. { ".P.K..K.", "..K.K...", "..K.....", "........", "........", "..K..K..", "..P....P", "........" }

    Returns: 4

  48. { "K..K....", "..K....K", ".....P.K", "......PP", ".....PP.", "..P..P..", "....PP..", "....K..." }

    Returns: 10

  49. { "..P.....", ".P......", "...P...P", "K..P....", "...PPP..", "........", "........", "...P...." }

    Returns: 16

  50. { "......K.", "P.......", "....P..P", "...P..K.", ".P..PP..", "....P...", "........", "P......." }

    Returns: 17

  51. { "..P.P...", "........", ".......P", "PP......", ".P.KP...", "....P...", "........", "......P." }

    Returns: 18

  52. { ".....P.P", "P.P.....", "..P.....", "........", "...P....", "..K..PP.", ".P......", "........" }

    Returns: 19

  53. { "P....P..", "....PP.K", "....P..P", "........", ".....P..", "........", ".....P..", ".P......" }

    Returns: 21

  54. { "...P...P", ".....P..", "...P....", "K.......", "....P...", ".......P", "...P....", "P.P..P.." }

    Returns: 22

  55. { "P....P.P", "P.......", "......P.", "PPP.....", "........", "........", "........", "K...P.P." }

    Returns: 23

  56. { "P...P..P", "........", "......PP", ".P..P...", "........", "......P.", "....P...", "..P....K" }

    Returns: 24

  57. { ".P..P..P", "........", "....P...", "........", "........", "K..P....", "P......P", "P..P...P" }

    Returns: 25

  58. { "P..P...P", "........", "P.......", "...P....", ".......P", "..K.....", ".P...P..", "..P....P" }

    Returns: 26

  59. { "P...P..P", ".......P", ".....P..", "...P....", "........", "P..P....", "........", "P...K..P" }

    Returns: 27

  60. { "......P.", "P...PP..", ".......P", ".....K.K", "P.P.....", "........", "P......P", "...P...." }

    Returns: 22

  61. { ".P..P.P.", "........", "........", "P...P...", ".......P", "K...PP..", "..P.....", "P......K" }

    Returns: 23

  62. { "P......P", "........", "....P.P.", "P.......", "..KK....", "P.......", "P.K.P..P", ".......P" }

    Returns: 20

  63. { "......K.", "P..KP...", "....K...", "..P....P", ".PK.....", "PP......", "...P....", ".P.....P" }

    Returns: 19

  64. { ".P...P.K", "...K.P..", "P..K.K..", "K.......", "........", "...PP..P", "P.......", "......PP" }

    Returns: 18

  65. { "P..P...P", "PK......", "........", "..K.....", "P...K.P.", ".PP.....", "....K...", ".KK.P..P" }

    Returns: 19

  66. { "P.P.....", ".K......", "P.P.K...", "....KK..", ".KK....P", "P....P..", "..P.....", "P..KP..." }

    Returns: 17

  67. { "..P.PK..", "....K..K", "K....K.K", ".P.K.P..", "...P....", "...P....", "...K.P.P", "P..P...." }

    Returns: 15

  68. { ".P...K..", ".....P.P", "....KP..", "..PKKP..", "........", ".KK.K...", "K.......", "P.PP...P" }

    Returns: 16

  69. { "K.PK...P", ".....P..", "...P...P", "KP...K..", "...P....", "........", "KP.KKP..", ".K..PK.." }

    Returns: 15

  70. { "K..PP.P.", "...K....", ".KKP..KP", "....P...", "...K..P.", "P.......", "......KK", "P..K..PK" }

    Returns: 15

  71. {".....P..","........","P....K..","..PPP...",".P..K.K.","P.....K.","P...P.P.","......K."}

    Returns: 14

  72. {"....P...","..P..P.P","P....P..",".PKP....","........","........","........",".......P"}

    Returns: 17

  73. {".......P","..P.....","........","....KP..",".P.P....","..P.P...","....P...",".....PP."}

    Returns: 18

  74. {".P......","..P.P...","........",".....P..",".KP.....","....P...","........","P.PP..P."}

    Returns: 19

  75. {"..P....P","P...P...",".....P..","........","..P.....",".P...KPK","........","P...P..."}

    Returns: 20

  76. {".P....P.","....PK..","..KP....","........","..P..P.P","P.....P.","........",".PK....."}

    Returns: 15

  77. {"P.K...P.","...P....",".K......","P....K..",".PP..P..","........","...PP.P.","......K."}

    Returns: 15

  78. {"....P.P.", "........", ".PK.....", "P.......", "P.K....K", "....KP.K", "P......P", "..P...P."}

    Returns: 15

  79. {".....K..","........","..P..PK.","....P..P","P.P.K...","..K...P.","..PK...P","......PK"}

    Returns: 12

  80. {"..K...P.","..P.....",".P...KK.",".P...PP.",".KP..K..","..P.....",".P....P.","K......."}

    Returns: 12

  81. {"KK.....P","...P...K",".PP...K.","..KP....","...K....","....PK..","P..P..PP","........"}

    Returns: 13

  82. {"K.P..P..","..K.KP.K","..K..K..","P.......","P..P....","KP.P...P","....K...",".......P"}

    Returns: 13

  83. {"K...P...",".K...K..","PKK...PP",".......P",".......P","P..K..K.",".PK.P...","..P...K."}

    Returns: 10

  84. {"P.P.KK.K",".P..P...",".KP.PK..","P.P...K.","....KK.K","K...P...","P.......","........"}

    Returns: 12

  85. {".P...PP.","........","...PP.KP","K...K...","..KP..K.","P.K.P.KP",".......K","....KK.."}

    Returns: 13

  86. {".......P",".PP.P...","P.....K.","...K.P..","...P.KPP","....K...","..KK.K.K","..P.KK.."}

    Returns: 13

  87. {".P.K..K.","K.K....K","....PP..","........","..P...P.","...PP...",".P......","P.....P."}

    Returns: 16

  88. {".P...K.K",".KK.K..K","...P...P","........","...PP...","..PP....",".....PP.",".P......"}

    Returns: 14

  89. {".KKK...K","K.PKP.K.","..P..PP.","........","....P...",".....P.P","...P..P.","........"}

    Returns: 13

  90. {"KP.K.K.K",".KPKKK.P","........","........","...PP...",".......P","P...P...","..P..P.."}

    Returns: 17

  91. {"P.K.KKK.",".KKKKK..","PPP.P.P.","........","....P...",".....PP.","..P.....","........"}

    Returns: 13

  92. {"KKK.KKP.",".KPKK.KK","P.......","........","..P.....","......P.","..PP.P..","PP......"}

    Returns: 14

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: