10977 - Enchanted Forest

Difficulty : medium

Solution Description :

BFS Problem with some extra work

1. For each block location(R,C), set grid[R][C]=false
2. Jigglypuff at location (R,C) having loudness L blocks all grid points (r,c) satisfying: (R-r)^2+(C-c)^2 le L^2. so, you do not need to use floating point. If (r,c) satisfy then set grid[r][c]=false.
Now you got all unsafe location.
For input 
10 10
4
1 5
2 3
4 1
8 10
4
3 2 0
5 6 3
10 1 4
10 8 1
You got the grid is
0000100000
0010010000
0101111100
1001111100
0011111110
1001111100
1111111100
1111010001
1111000100
1111101110
Here 0=safe location, and 1=unsafe location.

3. Run BFS from stating location(1,1). For each location(x,y) you got 4 adjacency location (x,y-1),(x,y+1),(x-1,y),(x+1,y) , if the adjacency location is safe location then the adjacency push to queue.
4. If you can reach to final location then print length of shortest path.
5. If you can not reach to final location then print "Impossible." (without the quotes, but with the dot.)