알파-제트 습격

우주 해적 크라이스 선장은 인공적이고 보안이 매우 강한 행성 알파-제트의 지도를 최근 손에 넣었다. 그는 오래전부터 이 행성을 습격할 계획을 세워 왔다. 행성 전체는 2차원 평면 위에 놓인 모듈들로 이루어져 있으며, 각 모듈은 방 하나에 해당한다. 정수 좌표마다 모듈이 정확히 하나씩 있고, 모듈의 크기는 1 × 1 단위이다. 모든 모듈은 인접한 모듈 중 적어도 하나와 양방향으로 연결되어 있다. 임의의 두 모듈 사이에는 경로가 정확히 하나 존재한다. 결국 모듈들은 순환이 없는 직사각형 미로를 이룬다.

지도에는 크라이스 선장이 표시해 둔 모듈 몇 개가 있으며, 그는 표시된 순서대로 이 모듈들을 방문하려 한다. 거기서 무엇을 할 계획인지는 你가 알 바 아니지만, 이동 경로에서 지나는 모듈의 수를 구해 주면 큰 보상을 약속한다. 순환이 없으므로 그는 표시된 모듈에서 다음 모듈까지 항상 직접 연결된 경로를 택한다. 첫 번째 표시 모듈이 출발지이고, 마지막 표시 모듈이 도착지이다.

그림 A.1: 입력 2의 설명 그림

입력은 다음과 같다.

• 미로의 높이와 너비를 나타내는 정수 h와 w (2 ≤ h, w ≤ 1 000)가 적힌 한 줄.
• 미로를 ASCII로 나타낸 h + 1개의 줄. 각 줄은 2w + 1개의 문자로 이루어진다. 다음 규칙을 따른다.
  • 모든 행에서 홀수 번째 열(1부터 셈)에는 세로 벽 또는 공백이 있고, 짝수 번째 열에는 가로 벽 또는 공백이 있다.
  • 첫 번째 줄은 미로의 북쪽 벽이며, 가로 벽만으로 이루어진다. 이후 각 줄은 모듈의 한 행을 나타낸다.
  • 모듈은 짝수 번째 열마다 놓인다. 서쪽 벽과 동쪽 벽은 바로 이웃한 홀수 번째 열에 있고, 북쪽 벽은 같은 열의 한 줄 위에, 남쪽 벽은 모듈 자신의 위치에 있다. 벽이 없는 자리에는 공백이 들어 있다.
• 미로 뒤에는 정수 m (2 ≤ m ≤ 10^4)이 주어진다.
• 이어지는 m개의 줄에는 표시된 모듈의 좌표 x와 y (1 ≤ x ≤ h; 1 ≤ y ≤ w)가 하나씩 적혀 있다. 첫 번째 좌표가 출발지이고, 마지막 좌표가 도착지이다. 같은 모듈이 여러 번 나올 수 있으나, 연속해서 두 번 이상 나오지는 않는다. (1, 1)은 왼쪽 위 모듈이고, (h, w)는 오른쪽 아래 모듈이다.

미로는 벽으로 둘러싸여 있다. 임의의 두 모듈 사이에는 경로가 정확히 하나 존재한다.

크라이스 선장이 주어진 순서대로 경로를 따라갈 때 지나는 모듈의 수를 나타내는 정수 하나를 출력한다.