# UVa 10977

## Summary

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

## Explanation

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

## Gotchas

• When there's no path print "Impossible." (without the quotes, but with the dot.)
• Jigglypuff at location ${\displaystyle (R,C)}$ having loudness ${\displaystyle L}$ blocks all grid points ${\displaystyle (r,c)}$ satisfying: ${\displaystyle (R-r)^{2}+(C-c)^{2}\leq L^{2}}$. Using this inequality you can get rid of floating-point variables.

## Input

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


## Output

8