← 返回 doordash 的题目列表Nearest DashMart
类型：online_judge
Nearest DashMart
You are given an R × C city grid:
M: a DashMart location; it is traversable.
.: an open road; it is traversable.
#: a blocked road; it is neither traversable nor a valid stopping cell.
From a cell, you may move up, down, left, or right to an adjacent traversable cell. Each move has distance 1.
You are then given Q query locations. For each location, return the shortest distance to any DashMart:
Return 0 if the queried cell is itself M.
Return -1 if the queried cell is #, or if no DashMart is reachable from it.
Input Format
R C
R grid rows, each a string of length C
Q
Q lines: row col
Coordinates are 0-indexed, where 0 ≤ row < R and 0 ≤ col < C.
Output Format
Print one answer per query.
Constraints
1 ≤ R, C ≤ 1000
1 ≤ R × C ≤ 10^6
1 ≤ Q ≤ 10^5
The grid may contain no DashMart locations.
Example
Input
3 4
M...
....
...M
5
0 0
0 3
1 1
2 3
1 3
Output
0
3
2
0
1