Problem A
Pathfinding on Dragon Age Maps

Pathfinding algorithms are very common in video-games. One frequent use of these algorithms is to move non-playable characters more naturally and efficiently through the game scenarios. As this needs to be done without ruining the game experience, a lot of effort is put into implementing very efficient algorithms for this type of problem.

In this assignment, you are going to implement a pathfinding algorithm on maps from the game Dragon Age: Origins. Each problem that you are going to solve corresponds to a map from one of the levels in the game. You will need to find shortest paths between different points of the map. The problems are from the pathfinding benchmarks by Sturtevant (2012).

In each instance, you will be given a grid graph and a list of queries. The grid contains free cells – cells that you can pass through – and blocked cells – cells that you cannot pass through, such as walls or trees. A query has two points (defined by their coordinates in the grid), and the goal is to find the path with cheapest cost between these two points.

There are some important details about these paths though: You can move orthogonally (up, down, left, right) or diagonally. When moving diagonally, you can also cut corners. In other words, you can go from cell $(x, y)$ to $(x+1, y+1)$ even if $(x+1, y)$ and $(x, y+1)$ are blocked! However, moving diagonally has a cost of 3, while moving orthogonally costs only 2.

Can you implement an algorithm more efficient than the one used in the game?

Input

The input starts with two natural numbers $H$ and $W$, the height and the width of the map respectively. The next $H$ lines describe the map. Each line contains $W$ characters each corresponding to one cell in the map. The first character of the first line describes cell $(0,0)$, the second character of the first line corresponds cell $(1,0)$, and so on. If the character for cell $(x, y)$ is . then the cell $(x, y)$ is free, otherwise it is blocked.

The first line after the map description contains a single natural number $Q$ describing the number of queries for this map. Each of the following $Q$ lines contains four natural number $x_1, y_1, x_2, y_2$ corresponding to the query for the shortest path from $(x_1, y_1)$ to $(x_2, y_2)$. It is guaranteed that $(x_1, y_1)$ and $(x_2, y_2)$ are free cells, and that there exists a valid path between them.

Output

Output should contain $Q$ lines, one for each query. For a query $x_1, y_1, x_2, y_2$ the corresponding output line should contain a single natural number $C$, such that the cost of the shortest path from $(x_1, y_1)$ to $(x_2, y_2)$ is $C$.

Limits

• $0 < H, W \leq 1\, 000$

• $0 < Q \leq 10\, 000$

• $0 \leq C \leq 2\, 500$

5 5
@@@@@
@...@
@.T.@
@.T.@
@@@@@
3
1 1 3 1
1 1 3 3
1 3 3 3

4
7
10

6 6
@@@@@@
@...@@
@.T...
@.T...
@.T..@
@@@@@@
4
1 1 5 3
1 3 3 3
1 5 5 3
5 2 5 3

10
10
17
2