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

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Java 1.8s
Memory limit: 128M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Marcus is stuck in a -dimensional grid of size , consisting of . for walkable spaces and # for unwalkable spaces! He is at the top left corner (position and must travel to the bottom right corner (position ) through only walkable spaces. He can only move left, right, and down. In a path, let be the number of times he moves down, left, and right, respectively. Let the cost of the path be . Marcus wants to find a path from to 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 , the size of the grid.

The next lines will each contain characters, either . for a walkable space or # for an unwalkable space. The first character of the first line will be position and the character of the line will be position .

It is guaranteed positions and will be walkable (.).

#### Output Specification

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

##### Subtask 2 [75%]

No further constraints.

#### Sample Input

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

#### Sample Output

78

#### Explanation For Sample

The minimum cost path consists of moving down units, left units, and right units, for a total of .

• commented on Sept. 3, 2019, 6:54 p.m. edit 2

>:(

• commented on Sept. 3, 2019, 9:45 p.m.

every

• commented on Sept. 3, 2019, 9:46 p.m.

day

• commented on Sept. 3, 2019, 9:46 p.m.

Marcus

• commented on Sept. 3, 2019, 9:47 p.m.

strays

• commented on Sept. 3, 2019, 9:50 p.m.

further

• commented on Sept. 3, 2019, 9:53 p.m.

from

• commented on Sept. 3, 2019, 9:54 p.m.

god's

• commented on Sept. 3, 2019, 9:55 p.m. edited

light.

• commented on Sept. 3, 2019, 10:30 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Nov. 17, 2019, 12:37 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.