Minimum Keys to Escape

You are given an (n \times m) grid representing rooms in a building. Each cell in the grid is one of the following:

• . A free cell where you can walk.
• K A cell containing a key. When you step on such a cell, you automatically pick up the key.
• # A wall. However, some walls represent locked doors that can be unlocked using a specific key.

Some walls are actually doors. Each door is described by a quadruple of integers ((r_1,c_1,r_2,c_2)) representing two adjacent cells. If one of these two cells contains a key (i.e. is marked with a K), then that key is the one needed to unlock the door. In other words, when moving from cell ((r_1,c_1)) to ((r_2,c_2)) (or vice versa) into a wall cell, the door can be passed if and only if you have already collected the key located at the corresponding key cell.

Your task is to start at the top‐left cell ((0,0)) and reach the bottom‐right cell ((n-1, m-1)) by moving up, down, left, or right. Find the minimum number of keys you must collect so that there exists a valid path. If it is impossible to reach the destination, output (-1).

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers \(n\) and \(m\) separated by a space.
2. The next \(n\) lines each contain a string of length \(m\). Each character is one of '.', 'K', or '#', representing a free cell, a key cell, or a wall, respectively.
3. The following line contains an integer \(q\), the number of doors.
4. The next \(q\) lines each contain four integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) separated by spaces, describing a door between cell \((r_1, c_1)\) and cell \((r_2, c_2)\). If one of these two cells is a key cell, then that key is required to pass through the door (when moving from one cell to the other through a wall cell).

outputFormat

Print a single integer to stdout – the minimum number of keys that must be collected to reach cell ((n-1, m-1)). If it is impossible to reach the destination, print (-1).## sample

3 3
.K.
#.#
KK.
1
0 1 1 1

2