Statistics

Problem Statement for "CollectingRiders"

Problem Statement

A rider is a fantasy chess piece that can jump like a knight several times in a single move. (See notes for a description of how a knight jumps.) A rider that can perform a maximum of K jumps during a single move is denoted as a K-rider. For example, a 2-rider can jump once or twice during a single move, and a 1-rider is a traditional knight.


There are some riders of different types on a chessboard. You are given a String[] board representing the layout of the pieces. The j-th character of the i-th element of board is the content of the square at row i, column j. If the character is a digit K between '1' and '9', the square contains a K-rider. Otherwise, if the character is a '.', the square is empty. Return the minimal total number of moves necessary to move all the riders to the same square. Only one piece can move during each move. Multiple riders can share the same squares at all times during the process. Return -1 if it is impossible.

Definition

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

Notes

  • A traditional knight has up to 8 moves from a square with coordinates (x,y) to squares (x+1,y+2), (x+1,y-2), (x+2,y+1), (x+2,y-1), (x-1,y+2), (x-1,y-2), (x-2,y+1), (x-2,y-1), and can not move outside the chessboard.

Constraints

  • board will contain between 1 and 10 elements, inclusive.
  • Each element of board will contain between 1 and 10 characters, inclusive.
  • All elements of board will have the same length.
  • board will contain only positive digits ('1'-'9') and '.' characters.
  • board will contain at least one digit.

Examples

  1. {"...1", "....", "2..."}

    Returns: 2

    The 2-rider can jump from (2,0) to (0,1) in the first move, and then from (0,1) to (2,2) to (0,3) in the second.

  2. {"........", ".1......", "........", "....3...", "........", "........", ".7......", "........"}

    Returns: 2

    In 2 moves, we can move all the pieces to the cell initially occupied by the 1-rider.

  3. {"..", "2.", ".."}

    Returns: 0

    No moves are necessary.

  4. {".1....1."}

    Returns: -1

  5. {"9133632343", "5286698232", "8329333369", "5425579782", "4465864375", "8192124686", "3191624314", "5198496853", "1638163997", "6457337215"}

    Returns: 121

    Kind of maximal test.

  6. {"1..", ".1.", "..."}

    Returns: -1

    impossible

  7. {"1...1", "....."}

    Returns: 2

  8. {"1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111"}

    Returns: 266

    max answer

  9. {"..45.....5",".......5..",".........2","3.9......1",".....2....","..1.......","......68..","....1..9..","..........","......5..7"}

    Returns: 19

  10. {"..........","1....4.7..","9.2.......","....3.9...","......2.4.","3......9..","......8...",".....7..7.","...8....5.",".........."}

    Returns: 15

  11. {".1.....2..","6.8......8","....6.7...","..........","9.........","....16....","....1.....","..7.....2.","..86......","...1......"}

    Returns: 21

  12. {".........5","3.........",".....2.578","..4...1...",".....72...",".2........","...41....9",".........5","64..9..499","...4.....9"}

    Returns: 24

  13. {".........2",".16.1..6..","........34",".....6....","..21.3....","2......9..","78........","23.4......",".....7....","4........."}

    Returns: 24

  14. {".....31396",".37.......","..6.....8.",".8........","........3.","......3..8",".........2",".......4..","...9....7.","...17.4..."}

    Returns: 24

  15. {"281..5....",".99.....8.","....26.5..","598....1..","....6.....","........9.","...9.2...6","..2.......","..21...8..",".4..1.6..."}

    Returns: 33

  16. {"......7...","...49...5.","..........",".7........","..19.9....","..........",".43.572.9.","....3.....","6.........","2....54.1."}

    Returns: 22

  17. {"..........","..9..9....","..........","4.3.......","......7...","...1.3....","....2.6..2","7......9.8","..........","..7.4....2"}

    Returns: 17

  18. {"...7.7....",".5........","..6..63...","....9.....",".4...6....","..8....5..","6..6.9...7","....91.6.6","...6.7..28",".........."}

    Returns: 23

  19. {"213.9.3.87","..8.1.2..4","..5.8.81.2","9.3..2.2..","...175.4..",".1.....65.",".5.1...221","....4...86",".7367.1...","..74....8."}

    Returns: 55

  20. {"7.82.27..5","..9.735.56","..924..9..","....86744.",".94.47.6..","13.8...145",".7137.7431",".3.8664...","355247.76.","5...538..3"}

    Returns: 65

  21. {".7546.58.8","27.7..5.7.","6..1....8.","33.72.5.83","..1..3.42.","5978998.68","...1..99..",".....9.7..","...2.635.6",".23558.8.1"}

    Returns: 58

  22. {"73...971..","1..888....",".6532.2..4","...4....24","..71.27.6.","......3...","..6...6333","8377..919.","2.99276..7","...15.4768"}

    Returns: 56

  23. {"162....973","659....2.1","7....2.68.","1.447973.4","7.49472..7",".26.55.8..","31..496.3.","3.....4539",".8.6....65","39.4..1.37"}

    Returns: 67

  24. {"241.6.21..",".1.8422...",".11...47..",".....13...",".542.5..19","73..86.6.1","86.5..8.8.","88..33...2",".6..7...6.","..6....89."}

    Returns: 55

  25. {"4652.1..1.","3.6...8.16",".1852.2..7","3.5..73515","467.1716..",".7338895..",".54458.4..","....14..48","4...4.7..3","..24...7.4"}

    Returns: 68

  26. {"99246.938.","7.1574..26","...1.2..8.","..1..67.4.","27..585499","...9298...","4518.4.6.6","4.52...64.","..7.1..214",".634.85748"}

    Returns: 70

  27. {"13794654.3",".5..8....5",".4165.7239","...571...2","1..7.326..","3.9.....23","....556.6.",".7.1.5.67.","5.7.3.272.",".....7...8"}

    Returns: 59

  28. {"4..48.1...","2..276...5","....5.38.5",".4165.63..","1.44..18.2",".12.8.5..4","..8.4.6752","..........","2.3.8....3","56.1..75.6"}

    Returns: 57

  29. {"15547.4317","439872379.",".782452356","3968.92516","1652562..8","3585131598","68141..218","7599185894",".327957657","3518387255"}

    Returns: 111

  30. {"3996234424","4442382957","2.6.1.6327","728.679314","1647466885","9.5.572729",".239875365","3543553254","7333413824","97.2773..8"}

    Returns: 103

  31. {"5793558.43","42.7259878","33.2554566","86569843.3","7745263213","2.8..45715","177167.5.4","5344981581","9853.57573","14.4613.26"}

    Returns: 104

  32. {"8237388739","86.9123298","9136821564","3.2.8.4.87","2223443815","4336488723","4893881933","82.27.9363","72236.17.1","6.324..912"}

    Returns: 111

  33. {"6879226641","7.2177511.",".3387679.4","1.4866673.","4266184392","..85531144","499.436423","1976252338","..81216952","864413.322"}

    Returns: 115

  34. {"1313425.8.","127514713.","8464478343","61.9112319","26.5381138","5996564485","6418..7597","1467249846","916.71.63.","5713.12355"}

    Returns: 116

  35. {"679695.26.","4636447929","2685.22531","4965253539","2297915622","3653426524","633.91.385","579.646697","36447851.6","549378.179"}

    Returns: 102

  36. {"27885.4823","4273918.36","3466117894","9295268811","974596897.","3348976659","53994662.1","6997.53193","6.64479139","3.36765344"}

    Returns: 109

  37. {"3775657264","7285935211","1237.25542","7889337885","65.7455494","5.2.534946","9216291322","8325399592","5633212646","6856953597"}

    Returns: 111

  38. {"811533.1.4","8612211243","3828699715","6845791.4.","8756427734","398..21672","2983968918","8518958654","7843167.78","1324236265"}

    Returns: 119

  39. {"..........","......1...","....1.....","......1..1","..........","..........",".....1....","..........","..........",".....1...."}

    Returns: 11

  40. {"........11","..........","1.........","..........",".1........","..........","..........","..........","..........","...1......"}

    Returns: 13

  41. {"..........","..........","..........","..........","..........","..........","..........","..........","........1.",".........."}

    Returns: 0

  42. {"..........","......1...","..........","..........","....1.....","..........","..........","...1....1.","..........",".........."}

    Returns: 8

  43. {"..........","1.........","..........","..........","..........","..........","......1...","..........","..........","1........."}

    Returns: 7

  44. {"..........","..........","..........","1.........","..........","..1..1....","..........",".....1....","..........",".........."}

    Returns: 6

  45. {"..........","..........","......1...","...1......","..........","..........","..........","..1.......","..........","....1....."}

    Returns: 8

  46. {"..........","..1.......","1.........","....1....1","........1.","....1.....",".......1..","..........",".....1....",".........."}

    Returns: 17

  47. {"...1......","......1...","..........","..........","..........","..........",".........1","..........",".......1.1","......1..."}

    Returns: 14

  48. {"..........","..........","11........","..........","..........",".........1","..........","..........","..........",".......1.."}

    Returns: 11

  49. {"..........",".2....2...","......2...","1.........","...2.1....","...1......","..........",".......21.","..........",".........."}

    Returns: 14

  50. {"...3.1.3..","....2.321.","..2...3...","..32......",".......1..","...13.....","..........","......2.3.","..21..32..","......3..."}

    Returns: 28

  51. {"..1.......","...1......","....1.....","3......2..",".2........","..........",".....1....",".3.....2..","2......1..",".1..3....."}

    Returns: 22

  52. {"..2.1.1...","2..3...1..","..........","........3.","3......1..",".....2....","2........1",".....1.3..","..........","......2.1."}

    Returns: 28

  53. {"...3......",".1..32...2","..2.......","...1.12...","2..1.2.2.1",".......321","1.......1.",".....1....",".3...2....",".1...1...."}

    Returns: 44

  54. {"..........","..3....1..","..3.1.....","1.3.3.....","..........","..........","3......1..","....2...3.",".....2....",".........."}

    Returns: 17

  55. {"..........","...2......","........1.",".....1..1.","3......313",".2...2....",".........1","..2...2.13","..........","....13...."}

    Returns: 28

  56. {".......3..",".2...2....",".3...3...3",".....3....",".3.....3..",".....1....",".11.....3.","..1...2.1.","........2.","...1......"}

    Returns: 26

  57. {".....3.1.3","...22..12.","........22","1..3......","3........2",".....3....","1.........","..........","..........","..2..2...."}

    Returns: 28

  58. {"3.........","........3.","2.2.....2.",".....3....","....3....1",".3.....33.","...1......",".........3","..2....3..","..12.2...."}

    Returns: 24

  59. {"1.", "..", "..", "..", "1."}

    Returns: 2

  60. {"1.", "..", "..", "..", "..", "1."}

    Returns: -1

  61. {"1....1", "......"}

    Returns: -1

  62. {"........", "...1.1..", "........", "........", "........", "...1.1..", "........", "........"}

    Returns: 4

  63. {"9133632343", "5286698232", "8329333369", "5425579782", "4465864375", "8192124686", "3191624314", "5198496853", "1638163997", "6457337215" }

    Returns: 121

  64. {"...", ".99", "..." }

    Returns: -1

  65. {"232..11123", "323.323232", "23.1232323", "3232323232", "121.12121.", "3232323232", "1111653278", "21326.5487", "1914181613", "2323232323" }

    Returns: 139

  66. {".73363234.", "522367.654", "8323243369", "54..576782", ".578564375", "8194364686", "3129865557", "5134754353", "1356733997", ".87654551." }

    Returns: 103

  67. {"1...1", ".....", ".....", ".1.1.", "....." }

    Returns: 4

  68. {".1111" }

    Returns: -1

  69. {"123", "4.5", "678" }

    Returns: 7

  70. {"..........", ".........1", "..........", "..........", "..........", "..........", "..........", "..........", "..........", "9........." }

    Returns: 1

  71. {"1..", "...", "..1" }

    Returns: 4

  72. {"1..", ".1.", "..1" }

    Returns: -1

  73. {"..1..", "1...1" }

    Returns: 2

  74. {"..", "29", ".." }

    Returns: -1

  75. {"1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111" }

    Returns: 266

  76. {"1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "1111111111", "2222222222", "2222222222", "2222222222", "1111111111" }

    Returns: 233

  77. {"1.", ".1" }

    Returns: -1

  78. {"1....1", "..1..." }

    Returns: -1

  79. {"9..9" }

    Returns: -1

  80. {"1111" }

    Returns: -1

  81. {"99" }

    Returns: -1

  82. {"1...1", ".....", "1...1" }

    Returns: 4

  83. {"1.1", "...", "..1" }

    Returns: 4

  84. {".111" }

    Returns: -1

  85. {"999999999", "999999999", "999999999", "999999999", "999999999", "999999999", "999989999", "999999999", "999999991", "999999999" }

    Returns: 89

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: