Statistics

Problem Statement for "TeleportationMaze"

Problem Statement

There is a rectangular maze built on a two-dimensional grid. Each cell of the grid is either an empty corridor or a wall. A corridor is denoted by a period ('.'), a wall is denoted by a hashmark ('#'). You are given the String[] a that contains the map of the maze. Rows and columns of the maze are numbered starting from 0. The character a[r][c] represents the cell in row r, column c.

You are also given the ints r1, c1, r2, and c2. You start in the cell (r1, c1) and your goal is to reach the cell (r2, c2).

You have to move in steps. In each step you can take one of the following actions:

  • Walk to any of the four adjacent cells provided that the target cell is empty. This move takes 1 second.
  • Teleport to the nearest empty cell in any of the four cardinal directions. This move takes 2 seconds.

You are not allowed to make a move that would take you outside the maze.

If reaching the destination is impossible, return -1. Otherwise, return the smallest T such that it is possible to go from (r1, c1) to (r2, c2) in T seconds.

Definition

Class:
TeleportationMaze
Method:
pathLength
Parameters:
String[], int, int, int, int
Returns:
int
Method signature:
int pathLength(String[] a, int r1, int c1, int r2, int c2)
(be sure your method is public)

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • Each element of a will contain between 1 and 50 characters, inclusive.
  • All elements of a will have the same length.
  • Each character in each element of a will be either '.' or '#'.
  • Both r1 and r2 will be between 0 and |a|-1, inclusive.
  • Both c1 and c2 will be between 0 and |a[0]|-1, inclusive.
  • The origin and the destination will be distinct.
  • The origin and the destination will both be empty.

Examples

  1. {".##.", ".###", ".###", "...."}

    0

    0

    3

    3

    Returns: 4

    0##2 .### .### ...4 You begin in the cell labeled 0. The optimal solution is to teleport eastwards (to the cell labeled 2) and from there to teleport southwards (to the cell labeled 4). The above solution takes 4 seconds. For comparison, walking southwards three times and then eastwards three times takes 6 seconds total.

  2. {"#.", ".#"}

    0

    1

    1

    0

    Returns: -1

    In this situation you have no valid moves. All cells adjacent to the source cell are blocked, so you cannot walk anywhere. There are no other empty cells in your row or column, so you cannot teleport anywhere either. Thus, there is no way to reach the given destination.

  3. {"......", "#####.", "#.###.", "#####.", "#.###.", "#####.", "#....."}

    0

    0

    6

    1

    Returns: 5

    012... #####. #.###. #####. #.###. #####. #54... The digits in the map above show an optimal solution. Each digit corresponds to the number of seconds between the beginning and the moment when you reach that cell.

  4. {"##########","#.####.###",".#########","##########","##########","########.#",".#########","##########","####.#####","######.###"}

    8

    4

    2

    0

    Returns: -1

  5. {"##########","##########","##########","###.#.##.#","####.#####",".#####.###","#.####.###","##########","####.###.#",".##.#.####"}

    9

    0

    8

    4

    Returns: 12

  6. {"##########","#####.#.##","##########","####.###.#","########.#","##########","########.#","#.########","##.#######","########.#"}

    8

    2

    3

    8

    Returns: -1

  7. {"#.###.####","#.#....##.","###..####.","#.##..#..#","..##...#.#","###.#.#...","#.#.##...#",".###.###.#","##.#.###..","#.#.###.##"}

    3

    5

    2

    3

    Returns: 3

  8. {"...#####.#","#..##.....","#..#.#####","##.##....#","##.....##.","#####....#","##.##.#.#.","..###.#...","...###....","####.#..#."}

    8

    6

    3

    7

    Returns: 5

  9. {"##.#.....#","....#####.","...###..##","#.##.####.",".#.##.#.##",".#.##.####","##.###.#..",".##.##....",".#.##..##.","..###...##"}

    9

    5

    2

    6

    Returns: 6

  10. {"..........","...#.....#","#...##...#","..#..#.#..","..........",".#..##....","..........","......#...","#.#.##...#","..#......."}

    1

    0

    0

    8

    Returns: 9

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

    6

    2

    6

    9

    Returns: 7

  12. {"...#.#....","..........","#....#....","..#......#",".#..#.....","..........","...#.....#","..#..#...#",".#........","...#...#.."}

    6

    4

    2

    1

    Returns: 7

  13. {"##################################################","#####.######.############.################.#######","########.#########################.###############","#.###########.######.##.##########.############.##","########################################.###.#####","###.######################..##########.###########","##########.#######.#########.#####.##..###########","#############################..#######.###########","######################.###############.###########","#...###.##############################.###########","#############.############################.#######","#####..#.###################################.#####","###################.##############################","###########################################.######","##########.####################################.##",".#######.########.################################","##################.######.###.###.################","#####################.#######################.####","###########.#############.######.#################","######################################.###########","################################################.#","######.###########################.###############","##################################################","##################################################","################################################.#","#########################.########################","##########..#.###############.##############.#####","##################################################","###############.##############..#######.##########","#################################################.","################################################.#","#############.#########.##########################","############.#####.#############..####.###########","##########.########.##################.##########.","##################################################","###############.####..############################","##.################.####.#.#.######.#############.","##########################################.#######","########################.#########################","#######.###############################.##########","################.#################################","#########.###############.####.###################","##.###############################################","##########################.######.################","#############################.####################","####################.####.########################","##################################################","#####.######.#####################################","########################.########################.","########################.#########################"}

    7

    29

    15

    8

    Returns: 12

  14. {"#########.###.####################################","##.#.###############..############################","#.################################################","###########.########################.#############","####################################.#######.##.#.","#########################.########################","################.##########.#######.#####.#######.","#########################.###################.####","#########.##############.########.################","###################.##.###########################","############################.#####################","##.###.#################.#########################","#####.###########.######################.##.###.##","###.###.###################.###.#####.############","###########.######################################","###.#.############################################","###.##.#########.##############.#########.######.#","######################.##################.######.#","##################.#############.#################","#####.###############.####.##################.####","########.############.#################.##########","####################.############################.","##################################################","#################.########.#######################","##############.##########.#######################.","###############.############.#####################","####################################.###########.#","################.############################.####","###################################.#######.######","######.###################################.#######","#######.############.#############################","##################################################","###################.##########.####.########.###.#","###########################################.######","############################################.#####","#######.#####..#####.#####.####################.##","##################################################","###################.####################.#########","#################.#####.####.####.#############.##","########.########################.################","##.#############.#################################","#############.####################################",".#####################.#############.#############","###.##########.###############.##.####.########.#.","########.#########.###############################",".####.################################.###########","#########################################.########","#########.#############################.##########","#############.##################.##.##########.#.#","#############.##############..##########.###.#.###"}

    15

    5

    19

    45

    Returns: 8

  15. {"#########.################.###############.##.####","#######.################.#########################","################################################.#","########################.##############.##########","#####.############################################","###.###########.########################.#######.#","#..#############################################.#","######.#.#####################################.#..","############################################.####.","#######.#########.################################","#############.##############.#############.#######","#################.#################.###########.##","########.#########################################","#############..###################################","##################################################","###..####################.##########.########.####","##################################################","############.####.####.###########################","####################################.#############",".######################################.###.######","##############################.##################.","#################################.##############.#","######################################.######..###","####.####################################.########","#############################.####################",".#######################.######################.##","######.#################.######################.#.","########################.#########################","################.#################.#############.#","##############################################.###","################.###.##########################.##","##################.########################.######","##################################.###############","##############.#############.#####################",".####.############################################","#.#####.##############.###########################","########################.#########################","########.##.#######.##.###########################","##.###.####################.######################","######################.#########.##.########.#####","################################.#####.###########","#####################.#################.##########","#.################.################.#####.########","########.###########################.#########.###","##################################################","###.##############################.#####.#########","##################################################","##################################################","###.###########.####.#############################","######.###########################################"}

    31

    18

    35

    7

    Returns: 8

  16. {"####.######.######.#############.#######.#.#..#.##","########.######.#########################.###.####","####.###.#####.##.####################.########.##","#######.######.###########..####.###.#############","#######.#######.#.############.#################.#","###.#######.###########.#######################.##","#########.########.###.#####################.#####","#####.########.######..####.#####..###.##########.","################.#######.##########.############.#","#######.###################.#################.####","##.#####.#############.###################...###..",".############################.#.########..###.####","########.#.#######.#.####.#######.################","#####################.######.#####.#####.#########","#######.######.######.#.###.######################","######.#################.#.#################.####.",".#.####..###.#.#.################################.","########.############.#################.##########","################.##.####################.#########","######.#############.#####################.#######","###.##.##############################.####.###.###","##########################.###.#####.#########.##.","#####################.###########.######.#########","####.######.####.##.##############################","###############.##########.###############.######.","###############.############################.###.#","######.###.#########.################.#######.####","#############.######.########.######.##########.##","##.####.##################.############..#########","#################..#############.##.##############",".#####.###########.#.######.########.#####.######.","###############.##############.####.##############","################.#######################.#########",".#####################.#####.#################.###","###########.#####.#.#####..##.#######..######.####","##############.###..#####.#.#########.###.#.######",".#############..###.##############################","##############.########.#########.#############.##","###.#########.#######.#.#####.##########.########.","###############################.##########.#######","###########.#.##.############.#####.#######..#####",".##########.############.#######################.#","..###.#####.##..#####.#.#######.#####.##########.#","#.###.############################################","#######################################.###.######","######.############.####.###########.############.","##.#..##########.############################.####","#####.###.##############.####.####.##########.####","###.#.######..#####.##.#.##.########.###.#######..","##.####.##.###########################.####.######"}

    30

    0

    17

    8

    Returns: 8

  17. {"##.############..#######.#.##.####..#######.######","###########.#################.#########.####.#####","###.################.####.#########.########..##.#","####...########.########.#.#######################","##.#######.######.##########.#.###.##.###.#######.","###############.#.##########.###################.#","##.####.#######################.#.########.#######","##.########.####.#.##########.######.####.########","#####.####.#..#######.##############.#############","##.#############.####.##############.###.########.","########..######################..#.##############","##########.#.#####.##.############################","############.######.####...################.##.###","##########.###.######..############.#####.####.###","####################.#########.#####.#########.###","#.#######.#######.###.###.#####################.#.","######.###########.#####.#########..######.#######","#####################################.####.#######","############.###########.###############.#########","..############################..###.#.##.#########","###########.#######.####.############.############","###############################################.##","#######################.#.##.#########.#######.###","##.##################.#########.###.#.########.#.#","#####.#####.#.####################################","#######.########.#################.#########.###..","#############################.#.######.####.######",".##########################.#######.##############","####.####################################.#####.##","###.######.###########.###########################",".###########.###########################.#########","###.#####.##############..###################.##.#","###############.#####.#######.#.#####.##.#########","################.#####################.##.#.######","##.###################.##.#################.#.####","############.###.#.####.##############.###########","###################.#.#########.#.################",".#####..###################.###.###########.######","##############################.#.######.##########","######################.#######.###################","#.######.#####################.###.#.########.####","###.#######.##############.###.#.#########.#######","#.########..####.#.#####.#########.###########..##","####.###############.#####.####.##..##############","#..#######.#######################################","##..#.####.############...########################","####################.############.#.#############.","########################.###################.#####","########.###.#####################.###############","#.#.#####.######################.#####.####..#.#.#"}

    28

    41

    26

    31

    Returns: 8

  18. {"#########.#########..######################.####.#","..##################.########..######.############","##############.####################.#.##.#######.#",".##.#######.###################.#####.#######.####","#############################..#######.###..######","#.###############################.###.######.#####","#####.#########..#####.#####.####..########.######","###.#.###########.####################.###########","################.#########.##########.#####.##.###","#########################################..#######","#####.###########.##.####.##.######.#####.####.###",".##.########.####################.##.############.","############.##########################.########.#","#################.##########.#.###################","####..##..#######.#############.#########.########",".###.###############.###########.#################","######.###########.###############################","#########.#######.#########.###############.####.#","################.#.###########.####.##########.###","################.##.##.####################.######","#####..##############.###.#########.##############","######.###.#.######.#..###.##.####################","##########.##..##..##########.########.###.######.","##.##############.###########.###.#####.##########","##########.#########.##############..#############","####.##.########.###.##############.##.###########","####.###########.##.##.###########.#.##.##########","####.#####################.######.###.########.###","####.##.##.######.######.##.############.#########","########.#####.########.#########.#########.######",".#########.######..#.#################.#########.#","##.############.#####################.##..###.####","#######.#####.##################.#####.#.#########","#####################.#####.#########.###..##.####",".#.###.#.###################.######.##############",".####.##########.#.#########.####.########.#..####","#.############.#######################.##.#.#.#.##","##################.##..################.##########","##########.############.##########.####..####.####","############.####..#########################.#.###","##############.##############.####################","##############.###.######.##.#.####.#####.#######.","##############..####.#####.#########.#############","######..##############.############.##.###########","########.###.#########.###########################","############.#####.##############.#############..#","##.###################################.###########","##########.######.######.#######..##.########.####","################.####.#####.#####.######.#########","#############.##########.###.###########.#..######"}

    48

    40

    38

    40

    Returns: 2

  19. {"##.#.######.###.####.##.#####.####..##############","###########.#######.#..#########.#####..##########",".....#..#.##.#######################.###########.#","##..##################.####.###################.##",".###############.##.####.######.####.#.##########.","########################.#############.#######.###","#################.#######..######.#####.###.#.###.",".#####..###########.###########..#################",".#.############.###.###.#######.#######.#####.#.#.","#######.###.#######.#######.##############.#######","#.#################.#######..###########.#.##.####","####.#####.######.#####################.##########","#######.#########.#################.####.##.####.#","########..########.#####.#####.###################","#####.#..#.#####.###.##.##.##.#############.######","#####.##########.#####.#.#########.#..########.###","#.###########.################.#.######.#.########","########.#####..##################################",".##.##############.###############.##########.#.##","#############..#####..########.#############.#.###","#########.#############.##.#.#########.#.#####.###",".##.####.##################.######.####..#.######.","###.##########.#.######.####.#######.#####.#..####",".############.########.###########################","#########.####.######.#.##########################","############################.###############.#..##",".#####.###########.############.##.###.#########..","######.##############.####.#####.###..####.####.##","#.#..##.###.#################..#.########.########","######.#####.#######.#####.###.#.#########.###.###","#####.#.##############.#####.###############..###.","##.#############.#####.#########..################","###.#.########################.###################","#.###.######.#.######..#######.##.######...##.####","#########.#.##.##########.##.###..########.#######","####.###########.#########.############.#..###.###","#.#######..#############.########.##########.#####",".######.####.########.###.#######.#######.#.#.###.","###########.##.##############.##.##.#####.########","###########.#.#...#.##########.#####...#####.#####","#############.#..######...#########.##############","#.#####################.#.#.######..##.###..######","###.##################.######.##..###.##.####.####","#####.##.#############.##########.#######.####.###","###.##########.######.########.###################","#.###############.###########.############.##.####","#.##.#####.########.#####..####.#..##.#.###.#.####","##.#####..###.##.###.#.#######..###.###.##########","###########.#####.###..##.####.#.###.###..########","####..##.#############.#####################..#..."}

    19

    46

    45

    45

    Returns: 12

  20. {"#############.######.########.##.##.##.###.#######","##########.####.#.##.####.#####.########.#######.#","..##..#.######.##############.####################","####.#############.#######.########.#####.###...##","#######.##########.########.#######.##.###########",".########.####.#########.##################.######","###############################..#.######.####.###","########.########.#.##########.##############.####","#.####.######..####.###.########.####.####.#######","#####.#######..###.####.###############.####.#####",".######.#.##.#######.###..#..####################.","#####...##########.################.#####.####.###","###.###.#############.############################","##.#####.###..####.####################.#######..#","#.##.################.#.####.############.##.#####",".###.#########.#####.####.######.#################","###.##########.##.###..#.#######.############.####","############.##########..#############.###########","#############.#######.#####.#.#########.###.#..###",".#.########..###..##########..##.###.#############","#########.####.#.######.#####.################..##","######.##########################.###########.####","##.###########..##########.#.################.#.##",".########.......#####.###..##..#########.####.####","##.#.#############.##..#.##############..#########","#########...#####..############.####.######.####.#","####.#########.######.########.###..####.#########","#.######.###############################.########.","###.######.####.######################.#####.#####","##############.###.####..###############.####.####","#.#############..#...#########.####.###.#########.","#########.#####..###..##.#..#.##########.##.######","##.###.#####..##.##########.########.##.##########","####.#########.####...######.######.##############","##.#######.################.######################","#.##.###########..######.###.#.#######..##.#######","#########.################################.#.#####","#############.##.##.############.#############.###","###.#####################.##.###.###############.#","####.#.##.###.#.##.###########.##.#.###########.##","#####.######.##################.#.##.#############","#.##.##.##########.##.#.#########################.","####.######...###.############.############.##.###","####.#######.#.###.########.#############.########","#.###.#################.##.#####.############.####","####.##################.##############.########.#.","#######.##.###########.##########.####.###.#######",".####################.#####.####.################.","#############..####.###.#############...#####.#.##","#.#.##########.###.#######.#..######.#.#.##.###.##"}

    0

    35

    38

    25

    Returns: 10

  21. {"######################.#.#####..###.#############.","##.##.#####.###.###########.###############.#####.","############.###############################.#.###","#############.######################.########.##.#","#########.######.###..########.######.############","#.###############.##################.########.####","#.######.########.################.##############.","#.####.#..#############.####.####..##..######.###.","###.###.#############.###.###.##########.#.##.####","#######.###.######.#########.#########..##########","##.##...#.##..##.####..#..#####.####.############.","###########.#######.######.#.######.##.###.##.#.##","######################.#########.########.##..####","##.########.#############.#######.###########.####",".#######.##.#...#########.################.#.##.##","####.######.########.####################.###.####","#.#############.######.#.####################.##.#","###.###.##..###.######.#.###.####.##.#####.##.####","####....######.##.#.##.##.#.#######.########.#####","##.#####.################.###.########.##..##.####","#######.######.##############.####.########.#####.","####.######.#####..#####################.###.#####","########.########.######.##..####.#######.#.######","##.#####.######.#################.##.#..###..###.#","##################.##.######.######.########.###.#","#######.########.#.#.############..######.##.##.##","#####.###########################.##..#.####.#####","#####.####################.##.###.##.##.########.#","###.######.###########.########################.##","#.##...###.##########.#.#.###########..#.##.######","##########.####.##.######.#.#.#####.#.#######..#.#","####.########.###.###.####.#####################..","##.############.#######.#.#########.#.##.##.######","###.####.####.#####.###########.###.#####.########","##..###.#################..###..##.########.#####.","#.#############.####.#############################","#######.##.#######.#.##.#.########.###.#.####.####","###.##.#########.###.###################.####.####","####..#############.#######.##############.#######","#######..###.###########.#####.#################.#","####.###.#.########################.##..#.########","##############.########.###.#.#############..##.#.","#################..#####.#######..##########.#####","####.#####.##.###########.##.###############..##.#","##########.##########..#############.###.#########","##########.#####.#.###############.#########.#####","#########.#######################..##########.####","##.####.######.######..###########.#.############.","##.####.####..###############.######.#########.#.#","######.#.#.####.##########.##############.####.##."}

    11

    28

    49

    46

    Returns: 14

  22. {".#################.#########.#.######.########.###","##.####..############.#.#.##########..###..#######","####.##########.##############.#.######.##.#####.#","....#.########..##.###..##########.####.##.#######","###.##########.#######.#####..##.###########..####","#.############..###..##.#####.##############.#####","####.########..######...#.########.##.###########.","##.####..#.######.#.#############################.","..##..########.#.##.##.###.###.#.#####.###########","#..###.#########.#.#.#############.#####..######.#","##..###.#####.####.###..#.###.####################","###.############..##.#.##########.############..##","#########.#########.##############.####.##########","#####.######.###.###############.##...####.#######","#.##.######.#######.####.####.###...####.#.#######","#.########.#####..####.#######.####.#.#.#..#######","###.########.###.###.##.#######..###.#..###...#.##","##############.####.##.#######..############.###.#","##.##.###...#####.############.###.##.###.##..####","#.#######.#.#.###.#.#..##########.#######.########","#################.##.#########.##.####.##.####.##.","#.#..##############.#####.##.#.##.#.##############","######.##.##.#########.###########.########.######","#######.#.######.######.######.###.###########.###","###.#########.###.#.##.#######.#####.#############","################.####.############.###########.###","##.#.#.#######..##.##.######.###...#.#.######.##.#","##..#########.#########.#.########.#.....#########","#####.##.##.#.####.###.#..##########..###..####.##",".#########.####.####.##.#############.###.#####.##","########.####.#########..###.###.###.##.########.#","####.##.######.########..#.#######.###############","##########.###.##########.##########.####.#####.##","###.#.#####.#.#.#####.########.######.###.####.##.","##.######.########.##.##############.#.####..#####",".#.######.#.###.#############...####.###.#.#######","########.########.####..###.######.#####.########.","#############..#.##..###.###########.#.#...######.","####.###...#####.#####..#########..###..##.#######","#####.##.####.#...####..#########.#####.#.##.#.#.#","###.#.############.###.##########.##.########.##.#","#########################.###.####..####.#######.#","####.#.###.##.##############.#.###.##.#########.##","#.####.#########.###.#.#.########..##..#..###.#.#.","####.#########.#.#.####.###.#############.#.##.#..","##########################..#########.############","#############..###.####.#.#.######..###.##.#####.#","#####..###.##########.#.####.####.######.###.##.##","####################.#.####.###.#.###########..###","##.####.####.#..##.######.##.######.#########.###."}

    26

    32

    11

    47

    Returns: 12

  23. {"########.#.####.#.##.#####.###########.....#######","#.#.####.#..##.####.#.######.####.#####.#.##.####.",".##..####.##.###.##.###.##.#.#####.#..############","#.########.#.#############..##...#########.#.####.","##.#....#..####.#..###.############..###.#.###.###","####.##.#.###############.#########.##############","######.#.####.######.###########.#####..####.#####","###.###.####.######.###.###.#.####.##.#########.##","#.###.####.#######.##########.##..####..####.#####","########.##.###.#.#.####...#####.####.#####.######","######..#.#######..#.##########.###..#####.#######","########.#.##.###.##.#####.####.###.##.#.##.##.#.#","#########.#.##.#.#########.##########...#####.###.",".#####.#.##################..#..#############..#..","###.###.##.#############.########.##..#####.##.###",".#.######.###..#.####.####.#.#.#..#..#.####.######","#.#.#########.##.....##.#######.####.#######.#####","#####.###.##.########.##############.###.####.####","#####..####.#######...########.#..#.##..#..#...###","########.####.####.########.##.###################",".#######..#..######.############...#############.#","#########.##.###..#.###.##.#.##.##.#.#############","####.#############.#.##.####..##.##.######..#####.",".######.###.####.#####.###.########.#.#.####.###..","###.##############.##.#.####.######.###.##########","##..#..#######################.#..###.##########.#","..#####..########################.########.#######","#############.###...####..######.#####..######...#","################################.###.##.####.#####","..####.###.##.#.###.###..#########################","#####.################.####.#..################.##","###...########..#########.#.#..##..###.######.####","##########..#############.###########.#########.##","##.#########.##..#######.####.#..#.#####.#..#.#.##","########.#######.####################.###.#...####","#####.##.##.#.#########.######.#####..############",".##.#####.#.######################.###.#.#..######","##.#########.#.#######.#####.#.####.##.####.##.##.","#####.######.##..#..#.####.###.############..#####",".##.######.########.#######.#######.####.##..####.","########.#.###########.######.####..##.###########","####.##.####.#######.#.####.############..########","####.#.######.#####..##############.#########..##.","####.###############..###..####.#######.####.###.#",".#.###########.####.#######.##..###.#####...######",".##.....#######.#######.#.#...###.####.#######.###","#####.##..#######.##.####.##.#.#######.##.#.######",".##.##########.####..######.##.###.######.###.####","######.###.####.######.###.####.#####.#######.#.##",".#####.#..####.#####.###...#####.#.####....#####.."}

    42

    19

    21

    9

    Returns: 11

  24. {"##.####.###.#.##.#.#############.#################","####.#.###.#.##.###############..##.###.#.######.#","###.#.##.####.##.######.#.#########.####.#.###.###",".#####.########.##.#..##.#.#.#.##.#.###.#.########","#..#######.######...###...#####..#############...#",".######.######.######.#####.####..###########..###","###.##..##.###########.###.######.#.######.##.####","####.###########..###.####.#########..#.###.###.##","####.#########.#######.####..##########.##.##.##.#","######..####.#..#####.############.###..########.#","#.#.###...##...#.######.######.####.####.######..#","###.##############.##..#####################.#####","#.###.##########.##.###..#..#######.#.###.#####.##","#..###..###.#....##.#####.#######.#########.#####.","#########.##.#####.##############.##...##.#..####.","#.####..######.##################..###.#########..","###.#.#..####.####.#######.########.#.##########.#","#########.#################.##..###..####.#####..#","##.#.#####.###############..#####.#.####.######.##","##.#####.###########..###.##.#####.####.##.#######","#.######.####.####.##.#.##########.######.########","###.#.###.#####.###..##.#####.######.##..###.#####",".#######.#####.###.###.####.#######.####.###...###","#########.###.##.##.###.###..####.#.#######.###..#","##.#.#.##.##.#####.##.####.####.####.#######.####.","######.#########.#####.#######.#.###....###.######","#.#####.#.##..##.#####.########.###..####.###..#.#","#.####.#####.#.##########.#.###########..##.#.####","##.#############..#..####.########..##.#.#.#.#####",".####.#.##########.####..####.##.##..##.#.########","#.##.####.##.########.#.##.#.#.##################.","##.#..####..#....######.##.##..########.#######.#.","#######..#.#..###.#..#########.############.###.##","#.#.#..###..########.####.#####.############...###","###..#########.##.##.#...##.#.###.######.###..###.",".##...#######.#.##.###.#######.##.###.#.##########","##..#####.####..##.####.####################..##.#",".#######..######.##.##########.###.#.######.##..#.","##.###.#.##.###.#########.##########.#######.#..##","###.#######.#.#####.#######..########.############","###.#####.####.############.#..#..##.#######.#####","#.#######.#######..#####....####.##.####.######.##","#..######.###.#.##..###########################..#","####.##.##.######.##############.####.############","#####################.#####..#.#######..####.####.","######.#.#####..#.##.#..#.###.####..##.##.########","###.#####.#########.#.####.##########.#.#.###.###.","###########.##..##############.####.####.#.###.#.#","########.####.##########.##########..##########.##",".#.#..##.##.###.#####..#####.#####.##.###.###..###"}

    36

    45

    48

    8

    Returns: 14

  25. {"##..#####.###.##.######.##..#.##########.##.####.#","#.###################.###########.##.#############","#####.#.####.####..#######.##.########.###########",".#..#########.##############.##########..##.##.#.#","##########.##.#.#..###.###.##.#.#..###############","#..##.#####.####.##.#.#####.###.#.####.#.####.####",".######################.########.####..#######.###","#..####.####..###.###.#.##.#####.##########.###.##","####.##############..##.#########.#######.###.##.#","##########.###..####.#####.####.#############.##.."}

    2

    29

    4

    26

    Returns: 4

  26. {"####.####.###.##########..###....###.###..#######.",".#####.#.#.###...##########.############.###.##.##","#######.#..##.#.########..###########....##.######","################..#.#######.###########.####.#.###","#######.######..#.######.###########..######.###.#","#.#.##.#######.##.##########.##.#.###..###.###.###",".###.#######.########.###.#.##############.#.###.#","##....###.##.#############..#.#####.#.#.###.#.##.#","###...####.#####.##.###.####.###################.#","####..########.##.#.##.##################.#..#####"}

    4

    37

    4

    14

    Returns: 8

  27. {"#####.##.#.##.##############.##.##########.#####..","#######.####.#####.#.##.##.#######.####.####.##.#.",".#..#####..#..#########.###..######.####.###.#..#.","##.#####.###.#######.#####..######...#######.#####","########.##.#####.###.#########.#########.########","#.###.####.##.#.#.#####.#########.##.##.#.########",".###..####.#########.###########.####..##########.",".#.######.##.#############.######.######..#.#.##.#","#####.###.##..##.#.#####.###############..#.###...","#########.#.#.###.##.######.#.#############.#.####"}

    6

    38

    1

    34

    Returns: 13

  28. {"#.######.#","##########","####..#..#","#.#.######","###...####",".#########","##.#..##.#",".######.##","#######.##","##.####.##",".########.","..##..#.#.","#####.####","#######.##","#.####.###","######.###","##########","..###.#..#",".#..##.###","##.#####.#","#####.####",".#########","##########","#.########","###.###.#.",".######.##","###.######","#####.#..#","...#######","###.######","#########.","##########","..##.#####","######.##.","##.####.##",".###.#..#.",".####.####","###.##...#","####.#####","######..##","####.#.##.","#####.####",".###.###.#","#.######.#","##########","#.####.###","#####...##","##.####.##","#####.#.#.",".#####..#."}

    4

    5

    43

    8

    Returns: 13

  29. {"#.######.#","#.########","#####.###.","##.####.##","######..#.","#####.#.##","...#######","#.#.#.###.","###..###..","####..####","##########","###..#.###","#.##..###.","###.######","####.###..","#.####..##","#..###..##","#########.","###.######","##.#######","##########","##########","##########","#.#.#.####","######.###","###.#.####",".#########","###..#####",".#####.#.#","######.###","####..####",".####.###.","#.#######.","##########","##########","##.##.##.#",".##..#####","#..##.##.#","#####..#.#","###.##..##",".#########","##########","####.#.###","########.#",".#########","##########",".###.#####",".#######..",".#######.#","#.########"}

    42

    6

    18

    3

    Returns: 13

  30. {"###.###..#","#.####.#.#","##..#.##.#","#..##.#.##","#.######.#",".#####.###","##.#######","##.######.","#######.#.","###.######","###.######","##..#.#.##","#.####.##.","#.#######.","#####..##.","###.######","##.#.#####","#.########","##.###.###","##.##..###","##.##...##","#########.",".########.",".##.######","########.#","######.###","#######.##","#.########","#.#.######","###.#####.","#.#..##.##","#.#.##.###","##.#.#####",".###.#####",".#########","###.#.#.##","####.#####",".##..#####","##########","#######.##","#.###...##","##########",".#######.#","##########",".##..#.##.","####..##.#","#.########","#########.","###.#..###","###.#####."}

    2

    3

    35

    7

    Returns: 14

  31. {"######.#############.########.###################","########.####.##############.##################.#","#######..##.###.#######################.#########","##################.###################.##.#.#####","########.#######.#################.###..#######..","###############.###########.############....#####","####.#######.################..###########.#####.","#####################..##########################","##################.###.############.#############","###########..#########.##################.######.","##################.###.##########################","###################.##############.###.##########","#########.#..###.######################.#########","#..#######.##.##.##########################.###.#","############.#################.##################","######################.##.##.####################","##########.##.#################.#################","##########.#######################.#.#..#########","###.########..###################.###############","#.######.######.#########.#####..####.###########","############.####################################","###########.#####################################","#####.###########.##.######.##############.######","#########################.###########.###########","###.################.############.###.#####.#####","#############################.##############.####","################.#####.#########.##########.#####","#.#####.######.#.##########.####.#.#.######.#####","..###############################.###############","#########.######.#.#####.####.######.#####.######","####.####.#######################################","##.###.#.######.########..##########..###########",".###########.##.#.##############################.","##..#########.##############...#################.","######.######.##.#######.########################","###.#####.#######################################",".###############################.################","####.##########.#.########.#.#######.####.#####.#","###.###################.############.########.###","##############.###########.##.##.#############.##","####.############.###############.#######.#.#####","#################################################","#######.##.###############.##########.###.#..####","##############.#######.#############.##.#########","###.#.#########################.#######.########.","##.###############################.#############.","########.####.#######.###########################","######.#.#.#.##############.##.#####.#.#########.",".###.############.#####.#########################"}

    12

    9

    18

    33

    Returns: 10

  32. {"#####.############.###########.##################","#################################.###############","#######################.######.##########.##.####","##########################.######################","##########.#########..#####.#########.###########","#############.############.###########.#####.###.","##########.#########.####.########.##############","##.#############################.######.###.####.","##.#..#..#######..#.###########################.#","######.###############.#####.###.######.#########","##.#################..#######.#.#########.#######","###############.##.##########.###################","#########################..####.###########.#####","#####.##########.#####.########.##..####.####.###","####.##################...######.#####.##########","#########.###########..##.#######################","#####.##.#####.#####.#####.#############.########","##################.##...#.######.#######..######.","#########.####...#####.#..####..##########.##.###","#####.#############.######.###.###.##############","####..###.################.######.######.########","######.###.####.#########.###################.###","######################.###########.##############","######.#############.#####.###.########.#########","####.###.####.#####################..###.#######.","#####.#################################.##.######","#############################.####.###.####.#####","###.###############.########.###..######.##.#####","###############.########################.########",".##.##.###.########.####################.########","##################################.##.###.#######","###..##.#.####################################.##","##########.###############################.#.#.##","#########################################.#######","######################.###########.#.############","##########################################.######","##.####################.#####.###################","#########.#.###.###.#########.###############..##",".#########.######..#####################.####.###","#######.#...######.###.##.#######.####.####.#####","##########################..#####################","#########.##########.####.###############.#######","#.##.########.###.####.###############.#######.##","#########.#####..#####.########.###########.#####","#########.###.######################.#######.#.##","##.#####.#########..############################.","##.######.#####.########..##..###################","##.################.#########################.###","#########..####.#.#######...##.#######.##########"}

    39

    10

    9

    32

    Returns: 15

  33. {"################################.#####.##.#######","#####.####################.#####.#######.########","#.#.#############.########################....#.#","#######.##################.#.####.###############","###################.#############################","####..##############.############.##.#########.##","######.##.#######################.############.##","###.###.#################.##############.########","#######..#.#############.######.############.####","####.##########.######.##########################","##########..#.#######..##########.###############","########.######.##############.##################","##################################.############.#","#################################################","##################.###################..#########","##.####.###########.##.#.###########.############","######...###.##.##################.##.###########","####.###.###########..###########################","####.####.##############.#.#####...############.#",".#########.###.################################.#","############.##############.#####################","####.######..####################################","##########.########.#############################",".######.###########.#######################.#.###","############.################.#.##########.####.#","#.#.###############.####.########.####.####..####","#.#.#.###.###########.##########.#####.####.#####","########.#.############.##.######################","##########################.##.##############.####",".###########.##.########.########.#####.#.#######","########.##.#########################.########.#.","###.####.############.##..###.###.###############","##.#######.##################.#.##############.##",".####.#.##.######.###############################",".####.##.#########..#.###.########.######.###.##.","####################################.####.####.#.","##########.##############.#######################","##########.#####.########.###########..##########","#############################.###..#############.","############.###.##.###################.###.#####","#########.####.#########.####.###.########.######","##.##################.#..#######..###############","####################################.#.##########","####.#############.#########..###.###############","###.###########.########.################.####.##","#######..########################.#.####.########","####.#######################################.####","#.##############################.#############.##","#####.####.##.##########.###########.####.#######"}

    27

    23

    47

    1

    Returns: 9

  34. {"........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................"}

    18

    4

    2

    24

    Returns: 36

  35. {"........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................"}

    17

    6

    25

    36

    Returns: 38

  36. {"........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................","........................................"}

    4

    31

    7

    8

    Returns: 26

  37. {"..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........","..........",".........."}

    23

    4

    23

    8

    Returns: 4

  38. {".................................................."}

    0

    2

    0

    13

    Returns: 11

  39. {".........#.#......#....##..........#.#....#......."}

    0

    41

    0

    47

    Returns: 6

  40. {"#",".",".",".",".","#",".",".",".",".",".",".",".",".","#",".",".",".","#",".","#",".",".","#",".",".",".",".","#","#",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".",".","."}

    35

    0

    26

    0

    Returns: 8

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

    37

    0

    10

    0

    Returns: 27

  42. {"......","######",".####."}

    0

    0

    0

    5

    Returns: 5

  43. {"......","######",".####."}

    0

    5

    0

    0

    Returns: 5

  44. {".####.","######","......"}

    2

    0

    2

    5

    Returns: 5

  45. {".####.","######","......"}

    2

    5

    2

    0

    Returns: 5

  46. {".#.",".##",".##",".##",".##",".#."}

    0

    0

    5

    0

    Returns: 5

  47. {".#.",".##",".##",".##",".##",".#."}

    5

    0

    0

    0

    Returns: 5

  48. {".#.","##.","##.","##.","##.",".#."}

    0

    2

    5

    2

    Returns: 5

  49. {".#.","##.","##.","##.","##.",".#."}

    5

    2

    0

    2

    Returns: 5

  50. {"....",".##."}

    0

    0

    0

    3

    Returns: 3

  51. {"....",".##."}

    0

    3

    0

    0

    Returns: 3

  52. {".##.","...."}

    1

    0

    1

    3

    Returns: 3

  53. {".##.","...."}

    1

    3

    1

    0

    Returns: 3

  54. {"..",".#",".#",".."}

    0

    0

    3

    0

    Returns: 3

  55. {"..",".#",".#",".."}

    3

    0

    0

    0

    Returns: 3

  56. {"..","#.","#.",".."}

    0

    1

    3

    1

    Returns: 3

  57. {"..","#.","#.",".."}

    3

    1

    0

    1

    Returns: 3

  58. {"......",".####."}

    0

    0

    0

    5

    Returns: 4

  59. {"......",".####."}

    0

    5

    0

    0

    Returns: 4

  60. {".####.","......"}

    1

    0

    1

    5

    Returns: 4

  61. {".####.","......"}

    1

    5

    1

    0

    Returns: 4

  62. {"..",".#",".#",".#",".#",".."}

    0

    0

    5

    0

    Returns: 4

  63. {"..",".#",".#",".#",".#",".."}

    5

    0

    0

    0

    Returns: 4

  64. {"..","#.","#.","#.","#.",".."}

    0

    1

    5

    1

    Returns: 4

  65. {"..","#.","#.","#.","#.",".."}

    5

    1

    0

    1

    Returns: 4

  66. {"#.", ".#" }

    0

    1

    1

    0

    Returns: -1

  67. {".##.", ".###", ".###", "...." }

    0

    0

    3

    3

    Returns: 4

  68. {"..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".................................................." }

    49

    48

    1

    1

    Returns: 95

  69. {".#...#", "#...#.", "......", ".#...#" }

    0

    2

    2

    5

    Returns: 5

  70. {"..##.", "##...", ".##.#", "....." }

    0

    1

    1

    3

    Returns: 4

  71. {"...###.", "...###.", "..###.." }

    2

    6

    0

    0

    Returns: 6

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: