Attack on Alpha-Zet#11625
The space pirate Captain Chris has recently obtained a map of the artificial and heavily guarded planet Alpha-Zet, which he has long planned to raid. It turns out that the entire planet is constructed as a two-dimensional plane composed of modules, each of which serves as a separate room. At every pair of integer coordinates, there is exactly one module of size 1 \times 1 units. Each module is bidirectionally connected to at least one of its neighboring modules. Moreover, for any two modules, there exists exactly one path between them. Thus, the modules form a rectangular maze with no cycles.
On the map, Captain Chris marked several modules that he intends to visit — strictly in the given order. What exactly he plans to do there is none of your business, but he has promised you a fortune if you help determine how many modules he will have to pass through along the route (since there are no cycles, he will always choose the shortest path from one marked module to the next). The first marked module indicates the starting point of his journey, and the last one — the endpoint.
The first line contains two integers and w~(2 \le h, w \le 1000) — the height and width of the maze.
Then follow h + 1 lines describing the maze in ASCII graphics format. Each line consists of 2 \cdot w + 1 characters. The description adheres to the following rules:
In each row and column with an odd index (starting from ), there can be either vertical walls or spaces. Columns with even indices contain either horizontal walls or spaces.
The first line describes the northern boundary of the maze (which always consists only of horizontal walls). Each subsequent line describes a horizontal row of modules.
A module is located at each even-indexed column position. Its western and eastern walls are located at the immediately adjacent odd indices to the left and right, respectively. Its northern wall is located at the same column in the row above, and its southern wall is located at the same column in the row below. If a wall is missing, its place is occupied by a space.
After the maze description, a single integer m~(2 \le m \le 10^4) follows — the number of marked modules.
Each of the next lines contains two integers and y~(1 \le x \le h, 1 \le y \le w) — the coordinates of a module that Captain Chris wants to visit. The first pair of coordinates is the starting point of the journey, and the last one is the destination. A module may appear multiple times, but never twice or more in a row. The module is the top-left corner of the maze, and is the bottom-right corner.
It is guaranteed that the maze is connected. Moreover, there exists exactly one path between any two modules.
Print a single integer — the total number of modules that Captain Chris will pass through if he follows the route in the exact order specified in the input.
Example 1
Example 2