Processing math: 72%
Escape from the forest - MarisaOJ: Marisa Online Judge

Escape from the forest

Time limit: 2000 ms
Memory limit: 256 MB
Marisa got lost in the forest! The forest can be represented as a matrix of size n×n: - . represents empty area. - # represents a tree. - She can only move to empty cell. Marisa are currently facing South at position (1,1), and she can escape if she reaches (n,n). Each move, she can move 1 step forward in her current direction or turn left or right by 90 degrees. Her broom is so special that only turning cost her 1 magic power. What is the minimum power required for her to escape from the forest? ### Input - The first line contains an integer n. - Next n lines represent the forests, each line contains a string of length n. ### Output - Print the amount of power required, or print -1 if she has to spend the rest of her life eating mushroom in the forest. ### Constraints - 1≤n≤2000. ### Example Input: 4... Output: 2
Topic
Graph
Shortest path
Rating 1100
Solution (0) Solution