Vova Escapes the Matrix
Contest: Codeforces Round 910 (Div. 2)
Difficulty rating: 2600
Tags: brute force, dfs and similar, divide and conquer, shortest paths

Following a world tour, Vova got himself trapped inside an $$$n \times m$$$ matrix. Rows of this matrix are numbered by integers from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered by integers from $$$1$$$ to $$$m$$$ from left to right. The cell $$$(i, j)$$$ is the cell on the intersection of row $$$i$$$ and column $$$j$$$ for $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq m$$$.

Some cells of this matrix are blocked by obstacles, while all other cells are empty. Vova occupies one of the empty cells. It is guaranteed that cells $$$(1, 1)$$$, $$$(1, m)$$$, $$$(n, 1)$$$, $$$(n, m)$$$ (that is, corners of the matrix) are blocked.

Vova can move from one empty cell to another empty cell if they share a side. Vova can escape the matrix from any empty cell on the boundary of the matrix; these cells are called exits.

Vova defines the type of the matrix based on the number of exits he can use to escape the matrix:

- The $$$1$$$-st type: matrices with no exits he can use to escape.
- The $$$2$$$-nd type: matrices with exactly one exit he can use to escape.
- The $$$3$$$-rd type: matrices with multiple (two or more) exits he can use to escape.

Before Vova starts moving, Misha can create more obstacles to block more cells. However, he cannot change the type of the matrix. What is the maximum number of cells Misha can block, so that the type of the matrix remains the same? Misha cannot block the cell Vova is currently standing on.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \leq n,m \leq 1000$$$) — the dimensions of the matrix.

The next $$$n$$$ lines contain the description of the matrix: the $$$i$$$-th ($$$1 \le i \le n$$$) of them contains a string of length $$$m$$$, consisting of characters '.', '#', and 'V'. The $$$j$$$-th character of the $$$i$$$-th line describes the cell $$$(i, j)$$$ of the matrix. The dot '.' denotes an empty cell, the sharp '#' denotes a blocked cell, and the letter 'V' denotes an empty cell where Vova initially is.

It is guaranteed that the corners of the matrix are blocked (the first and the last characters of the first and the last lines of the matrix description are '#'). It is guaranteed that the letter 'V' appears in the matrix description exactly once.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$1\,000\,000$$$.

Output format:
For each test case, output a single integer — the maximum number of cells Misha may block.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the matrix is of the $$$3$$$-rd type. Misha can create obstacles in all empty cells except the cells $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$. There are $$$9$$$ such cells, and adding such obstacles does not change the type of the matrix.

In the second test case, the matrix is of the $$$3$$$-rd type. Blocking any cell changes the matrix type to the $$$2$$$-nd: one of the two exits will become unavailable for Vova. Thus, the answer is $$$0$$$.

In the third test case, the matrix is of the $$$1$$$-st type. No free cell exists (besides Vova's), so Misha cannot block any cell.

In the fourth test case, the matrix is of the $$$2$$$-nd type. Misha can create $$$3$$$ obstacles in cells $$$(5, 2)$$$, $$$(6, 3)$$$, $$$(6, 4)$$$ without changing the type of the matrix.

In the fifth test case, the matrix is of the $$$3$$$-rd type. Misha can create $$$4$$$ obstacles in cells $$$(2, 2)$$$, $$$(3, 2)$$$, $$$(4, 2)$$$, $$$(5, 2)$$$ or $$$4$$$ obstacles in cells $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(4, 4)$$$, $$$(5, 4)$$$ without changing the type of the matrix.

Example input:
8
4 4
#..#
..V.
....
#..#
3 6
#.####
#....#
####V#
3 3
###
#V#
###
6 5
#.###
#...#
###.#
#V..#
#.###
##..#
7 5
#####
#.V.#
#.#.#
#.#.#
#.#.#
#...#
#.#.#
3 7
#.....#
.#####.
#...V.#
5 8
####.###
#..V#..#
#...#..#
#...##.#
###.####
5 5
#...#
##.##
##V##
##.##
#...#

Example output:
9
0
0
3
4
10
12
5

Editorial:
To solve the problem for matrices of $$$3$$$-rd type, find the shortest path to $$$2$$$ closest exits with a modification of BFS. Block all cells not belonging to the path with obstacles.
For a matrix of type $$$1$$$, Misha can block all empty cells (except the one Vova stands on).
For a matrix of type $$$2$$$, Misha finds the shortest path to some exit with a single BFS and then blocks every other cell.
Matrices of type $$$3$$$ are more complicated. We want to find two shortest paths to the two closest exits and block the remaining empty cells.
But, notice how the paths will likely share their beginnings. We do not have to count those cells twice. Let's take a look at the vertex where the two paths split. If we first fix the vertex, finding the shortest path to Vova can be done by running a single BFS and precalculating the shortest distances from each cell to Vova. Finding the shortest path from the vertex to the two closest exits can also be done with BFS and precalculation. We modify the BFS, making it multi-source, with a source in each exit. Also, we will allow each cell to be visited twice (but by different exits). We will need to maintain the following data for each cell:
* How many times was it visited; * The last exit/source that visited it; * The sum of paths from all exits/sources that visited the cell so far.
Running the BFS with proper implementation produces the answer. When everything said is precalculated, we fix the vertex in $$$O(nm)$$$ ways (each empty cell can be a valid vertex), and then calculate the shortest path from Vova to the two closest cells in $$$O(1)$$$ per vertex.
Total complexity is $$$O(nm)$$$.
What is the maximum number of cells that Misha can block so each initial exit is still reachable by Vova? Solve under the constraints $$$n, m \leq 500$$$.