403792: GYM101306 E Secret Passage

The Martians have invaded EPFL. Five minutes ago, they were at Esplanade and started heading towards the EPFL metro station to destroy it so that no student can return home (no one likes taking the bus anyway, and walking is just too hard!).

You are currently at Esplanade, and you need to get to the metro station before they do. Luckily, you know some secret passageways and can perhaps take a shortcut.

You are given the map to EPFL as an n x m grid, with some obstacles. Esplanade is at the top left corner with index (0, 0), and the metro station is at the bottom right corner with index (n - 1, m - 1).

The Martians (and you) can move vertically or horizontally on the grid, and need 1 minute to go from one cell to another. The cells that are obstacles cannot be traversed.

You are also given k coordinates. These are the obstacles that you can walk (or run!) through but the Martians can't because they don't know about.

Can you get to the metro station before them?

The first line will contain three space-separated integers n, m and k (1 ≤ n, m ≤ 500; 1 ≤ k ≤ 10⁵).

Each of the next n lines will have a string s_i of length m, representing row i in the EPFL map. Each character in s_i will be either a '.' representing a clear passage or a 'x' representing an obstacle.

Each of the next k lines will contain two space-separated integers r and c, where (r, c) represents an obstacle in the original graph that you can use as a secret passage (0 ≤ r ≤ n - 1; 0 ≤ c ≤ m - 1).

All k (r, c) are obstacles in the original graph, and are pair-wise distinct.

The top left and bottom right corners of the EPFL map will not be obstacles.

Print on a single line the word YES if you can reach the metro station strictly before the Martians do. Otherwise, print NO.

5 5 1
.....
xxxx.
.....
.xxxx
.....
3 4

YES

5 5 1
..x..
...x.
x.x..
..x.x
.x.x.
3 4

NO

In the first example, the Martians need 16 minutes to reach the metro station. You, on the other hand, know the secret passage through (3, 4), which allows you to reach the metro station in 8 minutes. Even though you started 5 minutes after the Martians, you still arrive before them!

In the second example, neither you nor the Martians can reach the metro station. If only obstacle (0, 2) was also a secret passage, you would have been able to reach.