UVa 10977

From Algorithmist
Jump to navigation Jump to search

10977 - Enchanted Forest[edit]

Summary[edit]

Find length of the shortest path between two points on a 2D grid. Some of grid points may be blocked.

Explanation[edit]

It's another straightforward shortest path problem. BFS is the classical algorithm here.

Gotchas[edit]

  • When there's no path print "Impossible." (without the quotes, but with the dot.)
  • Jigglypuff at location having loudness blocks all grid points satisfying: . Using this inequality you can get rid of floating-point variables.

Input[edit]

5 5
5
1 2
1 3
1 4
1 5
2 5
1
4 3 1
0 0

Output[edit]

8