Under construction

Still being built. Things may change

Attack on Alpha-Zet

Time limit2sMemory limit512 MB

Summary
Given an ASCII-drawn perfect maze and a sequence of marked rooms, count the rooms Captain Krys walks through along the route in order.
Level

Medium5 of 10

Topics
Tree, Graph, BFS, Implementation
Solved
No attempts yet

Problem

Space pirate Captain Krys has recently acquired a map of the artificial and highly secure planet Alpha-Zet, which he has been planning to raid for ages. The whole planet is built on a 2D plane of modules, and each module is one room. There is exactly one module at every pair of integer coordinates, and each module is 1 × 1 unit in size. Every module is bidirectionally connected to at least one adjacent module. For any two modules, there is exactly one path between them. In all, the modules form a rectangular maze without loops.

On the map, Captain Krys has marked several modules that he wants to visit in the marked order. What he intends to do there is none of your business, but he promises you a fortune if you determine the number of modules he must walk through along the route. Since there are no loops, he always takes the direct route from one marked module to the next. The first marked module is where he starts, and the last is where he wants to finish.

Figure A.1: Illustration of Sample Input 2

Input

The input consists of:

  • one line with two integers h and w (2 ≤ h, w ≤ 1 000), the height and width of the maze.
  • h + 1 lines follow, describing the maze in ASCII. Each line contains 2w + 1 characters. The description always follows these rules:
    • In every row, columns with odd index (starting at index 1) contain either vertical walls or spaces, and columns with even index contain either horizontal walls or spaces.
    • The first row describes the northern wall of the maze, which always consists only of horizontal walls. Every subsequent row describes a row of modules.
    • A module is located at every even column index. Its western and eastern walls are located at the directly neighboring odd column indices, respectively. Its northern wall is at the same column index one row above, and its southern wall is at its own position. If a wall is missing, the corresponding position contains a space.
  • After the maze, an integer m (2 ≤ m ≤ 10^4) is given.
  • Each of the following m lines contains two integers x and y (1 ≤ x ≤ h; 1 ≤ y ≤ w), the coordinates of a marked module. The first pair is the start, and the last pair is the end. A module may appear multiple times, but never twice or more in a row. (1, 1) is the top left module, and (h, w) is the bottom right module.

The maze is enclosed. Exactly one path exists between any two modules.

Output

Output one integer, the number of modules Captain Krys must walk through if he follows the route in the given order.

Examples2

  1. Example 1

    Input
    2 6
 _ _ _ _ _ _ 
|  _ _ _ _ _|
|_ _ _ _ _ _|
5
1 5
1 1
1 6
1 1
1 5
    Expected output
    18

  2. Example 2

    Input
    5 5
 _ _ _ _ _ 
|_ _  |_  |
|  _| |  _|
| |_   _| |
|    _ _  |
|_|_ _ _|_|
7
4 4
1 4
3 1
4 5
1 2
2 2
5 4
    Expected output
    43