Back From Summer '19 P2: Straying From God's Light

Points: 7 (partial)

Time limit: 1.0s

Java 1.8s

Memory limit: 128M

Authors:

Problem type

Marcus is stuck in a $2$ $2$ -dimensional grid of size $N \times N$ $N \times N$ , consisting of . for walkable spaces and # for unwalkable spaces! He is at the top left corner (position $(1, 1)$ $(1, 1)$ ) and must travel to the bottom right corner (position $(N, N)$ $(N, N)$ ) through only walkable spaces. He can only move left, right, and down. In a path, let $D, L, R$ $D, L, R$ be the number of times he moves down, left, and right, respectively. Let the cost of the path be $D^2 + L^2 + R^2$ $D^{2} + L^{2} + R^{2}$ . Marcus wants to find a path from $(1, 1)$ $(1, 1)$ to $(N, N)$ $(N, N)$ that has the minimum cost.

Marcus wants to know the minimum possible cost. Please help him!

Input Specification

The first line will contain the integer $N$ $N$ $(1 \le N \le 1000)$ $(1 \leq N \leq 1000)$ , the size of the grid.

The next $N$ $N$ lines will each contain $N$ $N$ characters, either . for a walkable space or # for an unwalkable space. The first character of the first line will be position $(1, 1)$ $(1, 1)$ and the $N^\text{th}$ $N^{th}$ character of the $N^\text{th}$ $N^{th}$ line will be position $(N, N)$ $(N, N)$ .

It is guaranteed positions $(1, 1)$ $(1, 1)$ and $(N, N)$ $(N, N)$ will be walkable (.).

Output Specification

Output the minimum cost path for Marcus. If there is no path, output -1.

Constraints

Subtask 1 [25%]

$N \le 25$ $N \leq 25$

Subtask 2 [75%]

No additional constraints.

Sample Input

Copy

6
......
.#....
##.##.
......
.#####
......

Sample Output

Copy

Explanation For Sample

The minimum cost path consists of moving down $D = 5$ $D = 5$ units, left $L = 2$ $L = 2$ units, and right $R = 7$ $R = 7$ units, for a total of $5^2 + 2^2 + 7^2 = 78$ $5^{2} + 2^{2} + 7^{2} = 78$ .