Statistics

Problem Statement for "TwoRobots"

Problem Statement

There is a factory. The floor of the factory is a rectangle divided into unit squares. Some unit squares are walls, others are empty. You are given the plan of the factory: a String[] in which each '#' represents a wall and each '.' an empty square.

There are two robots in the factory: robot A and robot B. Their current locations are denoted 'A' and 'B' in the plan.

Both robots move synchronously at one step per second. In each step the robot must move from its current square to one of the squares that share a side with its current square. The robots cannot leave the factory, they cannot move to a wall, they cannot both move to the same square, and they also cannot trade spaces.

Robot A wants to reach location marked 'a' in the plan, and robot B wants to reach location marked 'b' at the same time. (The starting locations of both robots and their destinations also count as empty squares. The robots may enter them arbitrarily many times.)

Compute and return the minimum time in which both robots can reach their desired destinations at the same time. If that is impossible, return -1 instead.

Definition

Class:
TwoRobots
Method:
move
Parameters:
String[]
Returns:
int
Method signature:
int move(String[] plan)
(be sure your method is public)

Constraints

  • plan will contain between 1 and 40 elements, inclusive.
  • Each element of plan will contain between 1 and 40 characters, inclusive.
  • Each element of plan will contain the same number of characters.
  • plan will contain exactly one 'A', exactly one 'B', exactly one 'a', and exactly one 'b'.
  • Each other character in plan will be either '#' or '.'.

Examples

  1. {"Ab.a", "...B"}

    Returns: 3

    Robot A will make three steps right while robot B will step left, left, and up.

  2. {"#a#", "A.b", "#B#"}

    Returns: -1

    The two robots are unable to take the very first step: each of them has to go into the middle, but they cannot both go to the same square.

  3. {"#b#", "A.a", "#B#", "#.#"}

    Returns: -1

    Still no solution. Now robot B can start by going down, but there is no way to reach the two destination cells at the same time: one second before that happens they would both need to be in the same empty square.

  4. {"...", "#a#", "A.b", "#B#", "#.#"}

    Returns: 4

    A can go right, up, up, down while B goes down, up, up, right.

  5. {"AB......ab"}

    Returns: 8

    Both robots simply go right. Note that one robot may enter a cell the other robot left during the same second.

  6. {"bA......Ba"}

    Returns: -1

    The robots cannot swap spaces, so on this map they can never reach their goals.

  7. {"bA.......Ba"}

    Returns: -1

    This example is one square longer than the previous one. Again, robot A cannot move past robot B. On this map, this would involve both of them stepping onto the same square at some moment.

  8. {"AB.........", "...........", "...........", "........b.a"}

    Returns: -1

    Plenty of room for maneuvers, but it's still impossible for the robots to reach 'a' and 'b' at the same time.

  9. {"...A...", ".#####.", ".#####b", "B#####.", ".#####.", ".#####.", "..a...."}

    Returns: 13

    The two robots must essentially go around the walls in the same direction. (If each robot selfishly tries to follow the shortest path to their destination, they will collide in the top left corner.)

  10. {"baA.B...................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................"}

    Returns: -1

  11. {"baAB....................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", "...#####################################"}

    Returns: 1631

  12. {"ba#AB...................................", "##......................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................"}

    Returns: -1

  13. {"baA.....................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", "B..#####################################"}

    Returns: 1631

  14. {"baA.....................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".#######################################", "........................................", "#######################################.", "........................................", ".B.#####################################"}

    Returns: -1

  15. {"A","a","#","b","B"}

    Returns: 1

  16. {"A","b","#","a","B"}

    Returns: -1

  17. {"A","b",".","a","B"}

    Returns: -1

  18. {"..", "ab", "BA", ".."}

    Returns: 2

  19. {".Ba.", "#bA."}

    Returns: 1

  20. {"b###.", "a...#", "BA#.#"}

    Returns: 2

  21. {"a.", "..", ".A", "Bb"}

    Returns: 3

  22. {"...#a", "b.BA."}

    Returns: 2

  23. {"..Bb.", "a..A#"}

    Returns: 3

  24. {"..", "b#", "A.", "aB"}

    Returns: 3

  25. {"..B...", "a#bA.#"}

    Returns: 5

  26. {"###.", "ba#.", ".##.", ".#..", "B##A", "...."}

    Returns: 17

  27. {"....", "..aA", "..bB"}

    Returns: 1

  28. {".#...", ".ABa#", ".b#.#", "....."}

    Returns: 4

  29. {"....", "...A", "....", "..a.", "b...", "B..."}

    Returns: 3

  30. {"AB", "..", "a.", "b."}

    Returns: 4

  31. {"A.B", "b#a"}

    Returns: -1

  32. {"...B", ".baA"}

    Returns: 3

  33. {"b...", "..Aa", "#B..", "....", "....", "...."}

    Returns: 3

  34. {"....#", ".....", "A.B#.", ".#...", ".b.a."}

    Returns: 5

  35. {".....", "b.a..", "..A..", ".....", "B...."}

    Returns: 3

  36. {".b.", "..a", "B.A"}

    Returns: 3

  37. {"...", "a..", "#..", "..A", "...", "B.b"}

    Returns: 4

  38. {"....#..", ".#..B..", "..#...a", ".Ab..#."}

    Returns: 6

  39. {"#.#.#.a", "A...#..", "...bB..", ".......", "#..##.."}

    Returns: 9

  40. {"..#.#", ".b.B.", "#.A..", "....#", "....#", ".a...", "....."}

    Returns: 4

  41. {".B..a", "#b...", "#A..."}

    Returns: 5

  42. {"....", "....", ".#.a", "..B.", "#bA."}

    Returns: -1

  43. {"..a.", "..b.", "AB.#"}

    Returns: 4

  44. {".#b..", ".....", ".B.aA"}

    Returns: 3

  45. {"...b#.", "...#.#", "#.A#..", "B.#..a", "#....#", "...#..", "#....."}

    Returns: 8

  46. {".bA.", ".Ba.", "...."}

    Returns: 1

  47. {"b.....", "A#....", "#####.", "#B.#a.", "..##..", "..#.#."}

    Returns: -1

  48. {"...#a..", "...#b#.", "#AB....", "#......"}

    Returns: 5

  49. {".....B", ".A....", ".#.#a#", "#.....", "#b#.#.", "...#.."}

    Returns: 8

  50. {"...", "...", "..a", "..b", ".A.", "...", "#.B"}

    Returns: 3

  51. {".....", "...B.", ".....", ".#...", "....#", "a..Ab", "...#."}

    Returns: 5

  52. {"....", "aA..", "..B.", "....", "....", "b..."}

    Returns: 5

  53. {".#..", ".#bB", "#A..", ".a.."}

    Returns: 1

  54. {"#..", "aB.", "#Ab"}

    Returns: 2

  55. {"..A.#..", ".......", ".....#.", "....a..", "#.B#...", ".......", ".#...b."}

    Returns: 5

  56. {"a.B", "A..", ".b."}

    Returns: 3

  57. {"Aa.b.#", ".#.#.B", "......", "......", "#.....", "#.....", "##..##"}

    Returns: 3

  58. {".b..", "....", "....", "....", "...a", ".A.B"}

    Returns: 7

  59. {"...", ".a.", "...", "B..", "...", "bA.", "..."}

    Returns: 4

  60. {".bB", ".A.", "...", "a#."}

    Returns: 3

  61. {"...", "B..", "a..", "...", ".A.", ".b."}

    Returns: 5

  62. {"#..", "..b", "B..", ".aA", "#.."}

    Returns: 3

  63. {"...", "...", ".#.", "..a", "B#b", "A#."}

    Returns: 4

  64. {"...", "A..", ".b.", ".B.", "..a"}

    Returns: 5

  65. {"..#..B", "....#.", "..A...", ".b.#..", ".....a"}

    Returns: 7

  66. {".b.", ".B.", "...", "..A", "#..", ".#.", "..a"}

    Returns: 3

  67. {".B....", "......", "#..b..", "#....a", "..##..", ".....A"}

    Returns: 4

  68. {"..................#.......A...#.......", "...................#.#.#..............", ".........#......#......#..............", ".....#................................", ".....#................................", "..##....#.#..........#................", "...................#....##..#.........", ".............................#.#......", "...........................#..........", "..........#........#..............#...", "...#........#....#....................", ".#.........................#.....##...", "........#............................#", ".......#....#.........................", "...#...........#....##................", ".............#.#......................", "..................#..........#........", "#.#.......#.....#..#.................#", ".....................a................", "...............#..#.......#.#.#....#..", "............#.....................##..", "..................#..........#........", "........##....#.......................", "....#....#....................#.......", ".....#....#....................##.....", ".....#........##......................", ".........#...#........................", ".....#...#..................#.........", "#.#.........#..#.........#............", "......................................", "......#.........#....#................", "...#B......#..........................", ".......#.........#....................", "..........#b.....#....................", ".......#........................#....."}

    Returns: 23

  69. {"............##......#", "A#..#................", "...................#.", ".........#...#....B..", ".#...#......#.....a..", "..##....#.....#......", ".......#...#.........", ".....................", "..#...............#.#", "............#........", "..#..................", "...............b.....", "..#.......##......#..", "....#.......#..#..#.."}

    Returns: 21

  70. {"...........#....#....................", "#......b.............................", "........................#............", ".....................................", ".....#.#....................#........", "............#......................#.", ".......#.............................", ".......#.............#...............", "....................#...#...#.....#..", "........#.................#...#......", "......................#...#..........", ".........#....#..##...#.#..B.........", ".........#.......................#...", ".....#...............................", "..................................#..", "............#......#.................", ".....##...#................#.........", "...........................#.........", ".......#........#....................", "......#..................#..#........", ".............##..#.................#.", "...........#...#.....................", ".......#.....#.......................", ".........#...........................", "............a....................#...", "..#..#...............................", "...#.......................#...#.....", "....#..................#...........#.", ".#...................A...............", "...........................#.........", "..................#....#..#..........", "..........#......#..#.#..............", "#.....#.....#...............#........", "........#............................", "#.................#......#...........", "..#.....#...........#.....##.......#.", ".#........#...................#......", ".................#...................", ".........................#...........", ".#.................#................."}

    Returns: -1

  71. {".......#.............#.......", ".............................", ".#.............A...#a........", "#............................", "......#.........#.....#...#..", ".............................", ".............#......##.......", ".............................", "............#....#...........", ".........#...#......#........", "................#........#...", ".....................#.......", ".................#...........", "..................#.....#....", "............................#", ".#..........................#", ".................b......B....", ".#.......##...#.#............", "..................#.........#"}

    Returns: 7

  72. {"#.#.##.....##....", "...#..#.#.#......", "....#..#..#.....#", "#.....#..........", "....#....###.....", "...#.....B.#.....", ".#.....#...#...#.", "....#.......###..", ".#.......#..#.#..", "...##..#.....##.#", "####..a..........", "#........#.....##", "#...#..........#.", "..#.#..#....#.#.#", "....#.b#.....###.", "..#.....#..#.....", "......#....#...#A", "...#.............", ".......#.....#...", "...#..#....##.#..", "........#..#....#", "...#.#....#.#....", "...#.............", "#....#.#...#....#", "#.#.....#......##", ".#.......#.#....#", "............#....", "..#.#.##....#....", "#..#.#........#.#", "..........##....#", "....#.......#....", "....##...##.....#", "...#.#...##..#.#.", "##......#.#..#.#.", ".....#.....#.....", "##..........##...", "........#......#."}

    Returns: 16

  73. {".....#........##....#......b.A.........", "...##..a.......B....#.#..#...#.......#."}

    Returns: -1

  74. {".......................", "...........#..........#", "...........#.....a.....", "......#.......#....#...", ".......................", "#....#...........#...#.", "...................#...", ".....#.................", ".......................", ".A.....................", "............b..........", ".............#.......#.", ".......................", ".......................", ".......................", "..................#.#..", ".#.....................", "...#...................", ".......#.....#.....B..#", "...................#...", ".................#....."}

    Returns: 23

  75. {"........#.#..#..#...b..", "..........#.##.#..##...", "....#.....####....#####", ".....#.......#.#......#", "..#..#.#####..##.#..##.", "#...#.#.##......#....#.", ".....#.#........##....#", "##.#....#......##...a..", "..#.#...A.#.#..#..#...#", "..#...#.....##.........", ".##...#...#......#.....", ".#.....##......#...#...", "#........B###..#...#...", "........##.#........#.."}

    Returns: 25

  76. {".....#..#...........#.....#..#......#", "....#.#.#...##..###........#.........", "#...##.#...##.............#.......##.", "##.....#..#.#.#...#......#..#..#...#.", "...#.....#..#.##.#......#..#..#.#...a", ".##..###..#.##..#.........#......#.##", ".#.#......#..#.##.#.....#...#.#..#...", "#.#...#..##.#...#..#....b....#..#...#", "#.#.##....#.......#..##.....#.#..#..#", "..#.............#...##......#........", ".#....#...#.##...##.B.#....#.#...####", ".........#.......#....#.#........#A..", "#.###....##..#.#....###..#.###......#", ".#.......#.#...#....#...#........#...", "#..#..#..##...##.#.####....####.##...", "..#...#....##.#.#...#.###..##.#.##...", "#..#......#..#...#..####.......#..#.#", "..#.#.....#....#..#..#.......#...##..", "....###...##...##....#....#......#...", ".#....##...#.##.#....#.#.#.#.........", "......#...##..#......#..#.....#.##..#", "#.#.#.#....#.....#....#...##.........", "#......#....#..##......#..##.......#."}

    Returns: 15

  77. {"...#....###...", "..#..#.....#..", "........#...#.", "#.............", ".#.###....#.#.", "....##...#.#..", "..........##.#", ".##...#..#.#..", "....#.#.##...#", ".......#..#...", "....##.......A", "##...#.#..#.#.", "#.....#.....#b", "......#.#....#", "#..##.....#..#", ".##......##.##", ".#......##...#", "............a.", "....#.###.#...", "...##...###...", "...##......#.B", "..#..#.#....#.", "..#..#......#.", "#..#..#..#..#.", ".#.......#....", ".........##...", "..#.#..##..#.."}

    Returns: 16

  78. {"................................", "................................", "................................", "................................", "................................", "................................", "...........a....................", "................................", "................................", "................................", "....................b...........", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "................................", "......................A.........", "................................", "................................", "................................", "................................", ".B..............................", "................................", "................................", "................................"}

    Returns: -1

  79. {"##.#a....b", "....AB....", "......#..."}

    Returns: 5

  80. {"...#....................#....#...#......", ".#...#...........#...............##....#", "............#..#.#.....#....#..#...#..##", "..#.#.##.......#.........#..#..#.....#..", ".#....#.##.###.......#.###.#..##..#...#.", "#.......#....#...............#.#.....###", "#........#.#....#.#.a.#....#..#.#.b.....", "#.#......##.#.#.#..#............#....#.#", "#........#...#...........###..#..#.#.#..", "...#.#.........#..####.##..........#....", ".###......#........##.##..A....#..##...#", "##..#......#...##.#.........##..#.#..#.#", "B....#..#.....#...#.......#....#.#..##..", "..#..#..........#...............#.##.#..", "#........#........#....###...#..#......#", "....#......#.#..#.##..#...#.#.#.###..#.#"}

    Returns: 46

  81. {"...###....#.....#..##...#.######.", "#.#.#.#.....#.##...#.....#...#...", "...#b..#............#....###....#", "...#.#........#....#....##.......", "..#...#..#.#.#.#....#..##......#.", ".....#....##.#...#....#.A.#......", "...#..........#..........#......#", ".##......#.#...#..#.......#.##...", "#..#......#.............#..B....#", ".......#...###.#..##......#.....#", "......#......#..###..#........#.#", ".....#.#...#.....#....#..##......", "...##..#a..#....#.#.#.##..#....#.", "#.......#.#....#...#....###..##..", "....###.............###.#.#....#."}

    Returns: 31

  82. {"a..##...", "#...##.#", "B#..b...", "..##....", "...###..", "#A#.....", ".##.#.##", "##......", "...#....", ".#..##.#", "....#...", "...#....", "#......#", "...##...", "..#.#..#", ".....#.#", "......#."}

    Returns: -1

  83. {"...#..##.#", "...#...#B.", "##.#......", "....##....", "#...#.#.##", "....b.....", "..####....", "......#...", "#..##...#.", ".....#....", ".#........", "......#...", "...#....##", "..........", "..#...#...", "..#.##.##.", ".....##..#", "##...#....", "##....#...", "###...#.##", "#........#", "......#.#.", "..A.#.....", "..#...#.#.", ".#..#.....", "...#......", ".#........", ".###..#...", "........a.", ".........#", ".#...#..#.", ".....##...", ".........#"}

    Returns: 12

  84. {"..........#..", "......#.....B", "............b", "......##...##", ".........A#..", ".............", "............a"}

    Returns: 5

  85. {"............##..#....##..........#", "........#....................#...#", "...#.............#..#........#....", "................#...#.........#...", ".....#...............#......#...#.", "..#..###..#....#......#...##......", "..............#....#..............", ".......#........................#.", ".....#................#.........#.", "..#...#...........................", "...................#..#....a......", "..................................", "....#..#.......##.......#.....#...", "...#....#.........................", "##.......#....#.........#.....#...", ".............#............#.#A....", ".......#..............#....##....#", "..#............#..................", "........#..................#......", "......#.#...............#....#.#..", "..............#.#..#......#b...#..", "............#............#...#....", ".......#...........#......#.......", "...#...#.............#...##.......", ".....#...#.#...#......#..#........", "................#............#....", "..#.......#.....#..........#......", "...#....#..#......................", "..............##....#........##...", "......#.#.........#....#.#.#..#..#", "#.#.........#.............#.......", "....#......#...#....#............#", "...#............#..#........#...##", ".............##............#......", "..#......#.....#............#.....", "......B...........................", "#................#.#..............", "...............#.......#.........#", "............................#.#.#.", ".....#...............#............"}

    Returns: -1

  86. {"..#....", ".b.....", ".......", ".......", "...a...", ".......", "#......", ".......", ".....B.", "#......", ".......", ".......", ".......", ".......", ".......", ".......", "A......", ".......", ".#.....", ".......", ".......", "..#..#.", ".......", "...#...", ".......", "......."}

    Returns: 15

  87. {"....................................#.", "...............................B......", "......................................", ".........b.....................#......", "........A..........................a.."}

    Returns: -1

  88. {"......A.........#...##........", "......#......#...#...#...#..#.", "........#......#..##..#.....#.", "..#...#....#...............#..", "...#.....................#....", "#.##.....#.#...#..#.....#.....", "......#....#.....#...........#", "#....#............#B..a....#..", "......#..#...#........#.......", ".#.#.#.....#...##...#..#......", "...##.......#....#...###.#....", ".#..............#.............", ".......b......#........#.#....", ".............#...#.#.......#..", ".............#.......#..#....#", "..#........#..#.....#....#....", "...#.................#...#....", "......#.....#.#...........#..#"}

    Returns: 23

  89. {"#.......................", "........................", "........................", "................b.......", "...#.#.....#............", "........................", "................#.......", "........................", "........................", ".....#.................a", ".........#......#..B....", "....#...................", ".#......................", ".....................#..", "........................", "........#...........#...", "#..............#.....#..", ".#......................", "......#.........#.......", "........................", "........................", "....#...................", ".....#..............#...", "........................", "........................", "........................", ".......................#", "........................", "...........#............", "...........A..#........#", "...................#....", ".......................#", "..................#.....", "........................", ".........#..............", "........................", "........................", "........................", "................##......"}

    Returns: 32

  90. {".#..#......#..#.#.......#...##.", "....#...##.#...##..##.....A..#.", "a.#..#...#....#.#..#...##.....#", "...#...###.#.#.#..#..#.....##.#", "...#....##...#....#.#.#.....###", "..##..#.......##..#..#...#.#..#", "..#...#..#...##...............#", "...#..##...#....#......###..###", "..#...........bB......#.#...#..", "#...###....#.....#.#...#.#....#", "#...#....#...#...#..#.........."}

    Returns: 39

  91. {".#.##...#....#", ".....#........", "......##..##..", "#...#.#....#..", "...#..#.#...A.", "......#...#...", ".#...........#", "..#.........#.", "#.....#...#...", "...#.#.##.#...", "...........#..", "..a...........", "..#.##....##..", "..#..##.#...#.", "#............#", "..##.......##.", ".##.B..##..#..", "..#......#...#", "...###..##....", "........##....", "......#....##.", "#........#....", "#.#........##.", ".#...#.##.....", "....##..#.#.#.", ".....#...#....", "........#.#.#.", ".##.b#..#.##..", "..#....#...#..", ".......#..#.#."}

    Returns: 17

  92. {"...........", "....##.....", "#.#..#....#", ".##..A.#...", "...#.....#.", ".......#...", "#.#........", ".#........#", ".#.#..#....", "...#..##...", ".........#.", "#......#...", ".#...b.....", ".......#...", "..#........", "..#........", "####.......", "....##.#..#", "#...#......", ".#...#.##..", "......##...", ".#...#.#...", "..#..#..##.", ".....#.####", "..#.#......", "...#..#.a..", ".##........", "........##.", "..........#", ".#..#...#..", ".##....#...", "#.......#..", "....##.....", ".#.#....#B.", "....#.#...."}

    Returns: -1

  93. {"...#......A...#...#................", "..........#....#..#................", "..B..................b.............", "...............#......#.........##.", "......#............................", "......a......#.........##...#......", "....#..#.......................#...", ".#........#........#...##.........."}

    Returns: 19

  94. {"....#.....#", "...##.#.#..", "........#..", "...#....#..", ".....#....#", ".#.........", "#..#B....#.", ".##..#.....", ".......#..#", "...#....#..", "...#.......", "..a..b..#..", "......#....", "...........", "..#..#....A", "#..........", "...........", "#..........", "...........", "......#....", "........#.."}

    Returns: -1

  95. {".####..........", "##..#.....##...", "...###.#....#..", ".......a....#.#", ".#.#.....###...", ".#..b...#.#...#", ".......#.......", "#..B..##.......", "...#.#.#.#....#", "#......#.......", ".........#..#..", ".....#..#....#.", "....#.#..##.#..", "...............", ".#...##.#......", "##....#.....#..", ".....###.......", "........#.A..#."}

    Returns: 23

  96. {".........#..#..#............", ".#.#........................", "...................##.......", ".....#..#....#.##.........##", "...#.........#.#.##.....#...", "........#..............#...#", ".....#...........#..........", "...........##..#............", "....##.............###......", "...#.............#.........#", "#.#..#.........#...##.......", "..............#......#..#.#.", ".....#..#..b...##...........", "...............#...##.......", "..#...............#.........", "............#.......#.......", "............#...#...........", "#.#....#.......###..#.##....", "..............##.....#....#.", "...........#.......#.A......", ".....B.........#...#........", "........#.........#.#..#....", "...##.....#......#.#..#.....", "............#.....#.......#.", "....#.......................", ".#.........#.......##.....#.", ".....#.....................#", ".........#.......#.......#..", ".....##....................#", "...........#........#....#..", "..#...#..#..................", ".......#...a...#.....#......", ".....#.....#................", "..#........#.#....#.#....#.."}

    Returns: 22

  97. {"........#..#", "#....#..ba..", ".#.AB.##...."}

    Returns: 9

  98. {"#...#...a..#.", "#.....A#.....", "#...##B......", "....b...#....", ".........##.#"}

    Returns: 3

  99. {"........................B.............", "..................................A...", "......................................", ".a..b................................."}

    Returns: 35

  100. {"a#.#..#......", "..#####......", "#.#.#....###.", "......#......", "...#.#.......", "...#.B..#....", ".............", "...###..#....", "#..#.A....#..", "#............", "#........b#.#", "#.#........#.", "###.#.#..#.#.", "......#.....#", ".......#.#...", "..#..........", "#..#.#..#...#"}

    Returns: 15

  101. {".##.........A.#..#.B..###", "#.##...b.a...#..#......#.", "####.#.##........##......"}

    Returns: -1

  102. {".#..#....#..#......#..####.", ".##.#.....#..####.##.......", "............#.##......#....", ".......#.....#.........#.#.", ".#.#.....#..........B..#...", "...#.#.....#....#..........", "##.##............#.........", "#.....#.....#....###.#.....", "...........#.......###....#", "..........#.......##.......", "..#..#......#.........#...#", ".....#....#...##....###...#", "......#...#....#...........", ".......#............##..#..", "#..#.........#.#...#.......", ".#.#..#.#..#...............", ".........#..##...#...#.....", "#....#..................#..", ".#.....#....#.#.#.....##.#.", "......#..#........#..#...#.", ".....#.....#..#...#..#.#...", "..#......#......#..#.....#.", "..##..#...#...#b...#.##.#..", "...............#..#........", "...#......#............#...", "...........#..#............", "....#..........#.........##", "...#......#................", ".#.....#...##....#.....#...", ".....#...#.#.......##......", "#....##...............#....", "...#..#.a...........###.#..", "....#..##...#...#..........", ".#.#......#...#..A.#.......", ".#........##......#.#....#.", "...........................", "...##..#..#......#...#.....", "#......................#...", ".....#..##..#..###........."}

    Returns: 25

  103. {"....##.#.#..", ".#....##...#", ".......#.#..", ".......#.#..", "##........B.", "#...........", ".#..#...#...", "..##........", ".#..........", "..#...#.....", ".#.#...##...", ".......#...#", "............", "#..#........", "...#.#..#.#.", "#...........", "#.#.#...a#..", ".b.#....#...", "............", "...........#", "...........#", "..#.#.......", "##...##.....", "....#.......", "....#.......", "#.##........", "........#...", "............", "..#......#..", "...........#", "..A...#....#", "........##..", "...##.......", "....#..####.", ".....#......", "....#..#..#.", ".........#..", "............", ".....##.#...", ".........#.."}

    Returns: 22

  104. {"A..", "...", "#..", "...", "...", "...", "...", ".#.", "...", ".#.", ".ab", "...", ".#.", "B.."}

    Returns: 13

  105. {"....#............#.B...", "..#..##..........#.#...", ".........#.#.#....#...#", ".....#..#....#....#..#.", "#.......#.#...a.#..b..#", "##.............##......", ".#........#...#...#.#.A", "..##.#.........####.#..", ".#....#....#...#......."}

    Returns: 12

  106. {"#............#..", "........#.#.....", ".#.#.....#...##.", "................", "#.#............A", "#..............#", ".......#....#...", "..............#.", "##..........#.##", ".........#.....#", ".#.............#", ".......##....#..", "..##........#...", ".........#..#...", "....#......#...#", "....a.#.##......", "..............#.", "..............#.", "......B.........", ".....#..#..##...", "..#.#......#b..#", "#..#.#.........."}

    Returns: 22

  107. {".............#..B....", "......##...........#.", "..#........#.........", "......#......#.......", "..........#....#.....", ".......#...........#.", "............##.......", "#......#............#", "............#.##.....", "#..........##........", "...................#.", "...#..#.........#....", "...........#.......#.", "...#.#....#......#...", "b...#................", "......#.......#.##...", ".........#...........", "............#........", ".#..#.#....#.#....#..", ".....................", ".......A.............", "a..........#.......#.", "....#................", "...#.##..........#.#.", "..........#.......###", "...........#....#.#..", ".....................", "...............#.....", "...#..........##....."}

    Returns: 30

  108. {"..AB...................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".......................................", ".................................#.....", "...............#.......................", "..................#....................", ".....................#...............#.", "...............................#..b..a." }

    Returns: 73

  109. {"ab......................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "......................................BA" }

    Returns: 78

  110. {"........................................", ".A......................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "............................#...........", "...........................#a#..........", "..........##...............#.#..........", "..........#b...............#.#..........", "..........#.################.#..........", "..........#..................#..........", "..........##########.#########..........", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", ".......................................B", "........................................" }

    Returns: 51

  111. {"Ab.a", "...B" }

    Returns: 3

  112. {"A..a", "####", "Bb##", ".###" }

    Returns: 3

  113. {"AB......ab" }

    Returns: 8

  114. {"A.......................................", "b.......................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "......................................aB" }

    Returns: 77

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: