Statistics

Problem Statement for "CaptureThemAll"

Problem Statement

Harry is playing magical chess. In this version of the game, all pieces move the same way as in regular chess, but players can cast some magical spells. Unfortunately, Harry's opponent, Joe, has captured all of Harry's pieces except one knight; Joe, on the other hand, still has a queen and a rook. The only chance Harry has to win this game is to cast a spell, "Haste", that will allow Harry's knight to make several moves in a row. You should determine the minimal number of moves the knight needs to capture both the rook and the queen, assuming neither of them moves. You may capture them in either order - rook first or queen first.

You will be given a String, knight, containing information about the knight. You will also be given a String, queen, and a String, rook, giving you information about Joe's pieces. knight, rook and queen will be formatted as "cr", where c is a character between 'a' and 'h', inclusive, determining the column on the board ('a' is the first column, 'h' is the last), and r is a digit between '1' and '8', inclusive, determining the row (1 is the lowest, 8 is the highest).

Definition

Class:
CaptureThemAll
Method:
fastKnight
Parameters:
String, String, String
Returns:
int
Method signature:
int fastKnight(String knight, String rook, String queen)
(be sure your method is public)

Notes

  • A knight's jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if knight is in the (0,0) now, it can be in (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2) after his move.
  • The knight will capture one of Joe's pieces if it ends its move in the cell that the piece occupies.
  • The knight cannot jump out of the board.
  • A chessboard has 8 rows and 8 columns.

Constraints

  • knight, rook and queen will all be distinct.
  • knight, rook and queen will be formatted as "cr", where c is a lowercase character between 'a' and 'h', inclusive, and r is a digit between '1' and '8', inclusive.

Examples

  1. "a1"

    "b3"

    "c5"

    Returns: 2

    From "a1", the knight can move directly to "b3" and capture the rook. From there, the knight can move directly to "c5" and capture the queen.

  2. "b1"

    "c3"

    "a3"

    Returns: 3

    The rook and the queen are both 1 move away from the knight. Once the knight captures one of them (it doesn't matter which one), it can return to its starting location, and capture the other piece in one more move.

  3. "a1"

    "a2"

    "b2"

    Returns: 6

    The rook and the queen are close, but it takes 6 moves to capture them.

  4. "a1"

    "h8"

    "b2"

    Returns: 8

  5. "a1"

    "h8"

    "b1"

    Returns: 8

  6. "a1"

    "a8"

    "h8"

    Returns: 10

  7. "a5"

    "b7"

    "e4"

    Returns: 3

  8. "c8"

    "g6"

    "b7"

    Returns: 6

  9. "f5"

    "c1"

    "a3"

    Returns: 7

  10. "b2"

    "h4"

    "a1"

    Returns: 8

  11. "b6"

    "d3"

    "a5"

    Returns: 5

  12. "g7"

    "e3"

    "h6"

    Returns: 4

  13. "h8"

    "e2"

    "d2"

    Returns: 6

  14. "g2"

    "g7"

    "h8"

    Returns: 7

  15. "e4"

    "c3"

    "g1"

    Returns: 3

  16. "d1"

    "f1"

    "a8"

    Returns: 6

  17. "c3"

    "e6"

    "g6"

    Returns: 5

  18. "d2"

    "f4"

    "d8"

    Returns: 6

  19. "f1"

    "e4"

    "f5"

    Returns: 4

  20. "e3"

    "b2"

    "d7"

    Returns: 5

  21. "e8"

    "g3"

    "b6"

    Returns: 7

  22. "d1"

    "f5"

    "b8"

    Returns: 5

  23. "b8"

    "f3"

    "d1"

    Returns: 7

  24. "h6"

    "b8"

    "g5"

    Returns: 6

  25. "b2"

    "g4"

    "b5"

    Returns: 7

  26. "f4"

    "c5"

    "f7"

    Returns: 5

  27. "f4"

    "a3"

    "g1"

    Returns: 6

  28. "e6"

    "d1"

    "h8"

    Returns: 8

  29. "e3"

    "d3"

    "g3"

    Returns: 5

  30. "d3"

    "h3"

    "f5"

    Returns: 6

  31. "b7"

    "g4"

    "e8"

    Returns: 4

  32. "a8"

    "e1"

    "e2"

    Returns: 7

  33. "g6"

    "f2"

    "g1"

    Returns: 5

  34. "a6"

    "c8"

    "c3"

    Returns: 6

  35. "b6"

    "g6"

    "e6"

    Returns: 5

  36. "c2"

    "a1"

    "g7"

    Returns: 5

  37. "b1"

    "e1"

    "a4"

    Returns: 5

  38. "g6"

    "e1"

    "d2"

    Returns: 5

  39. "f3"

    "d2"

    "e5"

    Returns: 3

  40. "f2"

    "e8"

    "f8"

    Returns: 6

  41. "b3"

    "b8"

    "d8"

    Returns: 5

  42. "a6"

    "a4"

    "h1"

    Returns: 6

  43. "h3"

    "b7"

    "d2"

    Returns: 6

  44. "f5"

    "d4"

    "e6"

    Returns: 2

  45. "g7"

    "e6"

    "e4"

    Returns: 3

  46. "b6"

    "e8"

    "b2"

    Returns: 5

  47. "e6"

    "e3"

    "d1"

    Returns: 4

  48. "f5"

    "e6"

    "g2"

    Returns: 4

  49. "h8"

    "e2"

    "d2"

    Returns: 6

  50. "a1"

    "h1"

    "a8"

    Returns: 11

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: