Statistics

Problem Statement

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

Given a regular grid of size W x H with various squares blocked out, find a path from point (0,0) to point (W,H) that does not pass through any of the blocked-out squares. The path must consist only of 90-degree arcs (quarters of circles). The radius of each arc must be an integer, and therefore begin and end on an integer grid point. The tangents at each end of every arc must be parallel to the x or y axis.

Arcs may intersect the corner of a blocked-out square and even pass between two that share a corner (as shown in the examples below), but may not pass through the interior of any blocked-out square.

The grid will be given as a String[], with a '.' representing an empty square and a '#' representing a blocked-out square. For example, given the following 12 x 8 grid:

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

there is a path from (0,0) to (12,8) consisting of 4 arcs, as shown in the following figure:

Find the path that contains the fewest number of arcs, and return the number of arcs in that path. If there is no path, return -1.

Definition

Class:

Arcs

Method:

numArcs

Parameters:

String[]

Returns:

int

Method signature:

int numArcs(String[] grid)

(be sure your method is public)

Constraints

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

Examples

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

   Returns: 1

   A single arc of radius 2, centered at (0,2) or (2,0), forms a path from (0,0) to (2,2).

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

   Returns: -1

   There can only be a path between opposite corners if the dimensions of the grid are both even or both odd. In this case, the dimensions are 3 x 2, so no path exists.

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

   Returns: 7

   Seven arcs of radius 1 are required in this example.

4. { "." }

   Returns: 1

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

   Returns: 4

   This is the example in the problem statement.

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

   Returns: 5

   There is a path consisting of 5 arcs, as shown in the following figure. Notice that the path may cross itself:

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

   Returns: 1177

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

   Returns: 1177

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

   Returns: 1

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

    Returns: 2

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

    Returns: 7

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

    Returns: 7

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

    Returns: 9

14. { ".................................................." }

    Returns: -1

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

    Returns: 25

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

    Returns: -1

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

    Returns: 25

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

    Returns: 49

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

    Returns: -1

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

    Returns: 49

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

    Returns: -1

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

    Returns: 10

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

    Returns: 8

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

    Returns: 7

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

    Returns: 1

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

    Returns: 7

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

    Returns: 7