Statistics

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Given a regular square grid, with some number of squares marked, find the largest circle you can draw on the grid that does not pass through any of the marked squares. The circle must be centered on a grid point (the corner of a square) and the radius must be an integer. Return the radius of the circle.

The grid will be given as a String[], with each character representing a square. A '.' represents an empty square, and a '#' represents a marked square.

The circle may intersect the corner of a marked square, but may not pass through the interior. For example, given the grid:

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

two circles can be drawn with radii 1 and 5, as shown below:

Therefore, your method should return 5.

Circles may not extend outside of the grid, and must have a radius of at least 1. If no such circle exists, return 0.

Definition

Class:

LargestCircle

Method:

radius

Parameters:

String[]

Returns:

int

Method signature:

int radius(String[] grid)

(be sure your method is public)

Constraints

• grid will contain between 1 and 50 elements, inclusive.
• Each element of grid will contain between 1 and 50 characters, inclusive.
• Each element of grid will contain the same number of characters.
• Each element of grid will contain only the characters '.' and '#'.

Examples

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

   Returns: 1

   Only one circle fits in this grid -- a circle of radius 1, in the center of the grid.

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

   Returns: 5

   This is the example from the problem statement.

3. { ".........." }

   Returns: 0

   The grid must be at least two squares wide and tall in order for any circles to fit.

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

   Returns: 0

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

   Returns: 4

   A circle of radius 4 fits in this grid, as shown here:

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

   Returns: 0

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

   Returns: 24

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

   Returns: 5

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

   Returns: 25

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

    Returns: 24

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

    Returns: 6

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

    Returns: 11

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

    Returns: 0

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

    Returns: 0

15. { ".................................................." }

    Returns: 0

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

    Returns: 1

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

    Returns: 0

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

    Returns: 1

19. { "." }

    Returns: 0

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

    Returns: 1

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

    Returns: 1

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

    Returns: 0

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 3

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

    Returns: 25

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

    Returns: 4

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

    Returns: 5

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

    Returns: 5

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

    Returns: 24

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

    Returns: 5

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

    Returns: 4