### 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

0)

 ```{ "..", ".." }```
`Returns: 1`
 A single arc of radius 2, centered at (0,2) or (2,0), forms a path from (0,0) to (2,2).
1)

 ```{ "...", "..." }```
`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.
2)

 ```{ "....", ".##.", ".##.", ".##.", ".##.", "...." }```
`Returns: 7`
 Seven arcs of radius 1 are required in this example.
3)

 ``` { "....########", "###..###...#", "..##..#.##.#", "...##..#...#", "....#..#...#", "....#..###..", "....####.##.", "..........#." }```
`Returns: 4`
 This is the example in the problem statement.
4)

 ```{ ".....#................", "....#.................", "....#.................", "....#.....#...........", "....#.................", "....#....#.#..........", "....#.......#####.....", "....#.....#.....#.....", "....#.....#.....#.....", "....#....#.#....#.....", "....#....#.#.....#....", "....#....#.#......#...", "....#....#.#.##.#..###", "....#....#....#......." }```
`Returns: 5`
 There is a path consisting of 5 arcs, as shown in the following figure. Notice that the path may cross itself: #### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2944

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5858&pm=2944

legakis

#### Testers:

PabloGilberto , lbackstrom , brett1479

#### Problem categories:

Geometry, Search, Simple Math