Vova Escapes the Matrix (Codeforces 1898F)
Tags: Others, 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: 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: For each test case, output a single integer — the maximum number of cells Misha may block.

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.

Sample Inputs:
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##
##.##
#...#

Sample Outputs:
9
0
0
3
4
10
12
5

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * m + v

def bfs(s):
    q = [s]
    dist = [inf] * (n * m)
    dist[s] = 0
    for i in q:
        (x, y) = divmod(i, m)
        di = dist[i]
        for (dx, dy) in v0:
            (nx, ny) = (x + dx, y + dy)
            if not 0 <= nx < n or not 0 <= ny < m:
                continue
            j = f(nx, ny)
            if not z[j] and dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
    return dist

def bfs2():
    q = []
    for i in range(1, n - 1):
        if not z[f(i, 0)]:
            q.append(f(i, 0) << 1)
        if not z[f(i, m - 1)]:
            q.append(f(i, m - 1) << 1)
    for j in range(1, m - 1):
        if not z[f(0, j)]:
            q.append(f(0, j) << 1)
        if not z[f(n - 1, j)]:
            q.append(f(n - 1, j) << 1)
    (dist, v) = ([inf] * (2 * n * m), [0] * (2 * n * m))
    for i in q:
        (dist[i], v[i]) = (0, i >> 1)
    for i in q:
        (x, y) = divmod(i >> 1, m)
        (di, vi) = (dist[i], v[i])
        for (dx, dy) in v0:
            (nx, ny) = (x + dx, y + dy)
            if not 0 <= nx < n or not 0 <= ny < m:
                continue
            j = f(nx, ny) << 1
            if z[j >> 1]:
                continue
            if dist[j] == inf:
                q.append(j)
                (dist[j], v[j]) = (di + 1, vi)
            elif dist[j ^ 1] == inf and v[j] ^ vi:
                q.append(j ^ 1)
                (dist[j ^ 1], v[j ^ 1]) = (di + 1, vi)
    return dist
t = int(input())
ans = []
inf = pow(10, 9) + 1
v0 = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(t):
    (n, m) = map(int, input().split())
    z = [0] * (n * m)
    for i in range(n):
        s = list(input().rstrip())
        for j in range(m):
            if s[j] & 1:
                z[f(i, j)] = 1
            elif not s[j] & 8:
                (i0, j0) = (i, j)
    s = f(i0, j0)
    dist = bfs(s)
    (c, mi) = (0, inf)
    for i in range(1, n - 1):
        if dist[f(i, 0)] ^ inf:
            c += 1
            mi = min(mi, dist[f(i, 0)])
        if dist[f(i, m - 1)] ^ inf:
            c += 1
            mi = min(mi, dist[f(i, m - 1)])
    for j in range(1, m - 1):
        if dist[f(0, j)] ^ inf:
            c += 1
            mi = min(mi, dist[f(0, j)])
        if dist[f(n - 1, j)] ^ inf:
            c += 1
            mi = min(mi, dist[f(n - 1, j)])
    if c <= 1:
        ans0 = n * m - sum(z) - 1 - c * mi
        ans.append(ans0)
        continue
    d0 = bfs2()
    mi = inf
    for i in range(n * m):
        mi = min(mi, dist[i] + d0[i << 1] + d0[i << 1 ^ 1] + 1)
    ans0 = n * m - sum(z) - mi
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
if True:
    (standard_input, packages, output_together) = (1, 1, 1)
    (dfs, hashing, read_from_file) = (1, 0, 0)
    de = 1
    if standard_input:
        import io, os, sys
        read = io.BytesIO(os.read(0, os.fstat(0).st_size))
        input = lambda : read.readline().decode().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args):
            print('\x1b[92m', end='')
            print(*args)
            print('\x1b[0m', end='')

def main():
    (n, m) = MII()
    grid = [I() for _ in range(n)]
    (sx, sy) = (-1, -1)
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'V':
                (sx, sy) = (i, j)
    dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    vis = [[0] * m for _ in range(n)]
    vis[sx][sy] = 1
    stack = [(sx, sy)]
    while stack:
        (x, y) = stack.pop()
        for (dx, dy) in dirs:
            if 0 <= x + dx < n and 0 <= y + dy < m and (not vis[x + dx][y + dy]) and (grid[x + dx][y + dy] == '.'):
                vis[x + dx][y + dy] = 1
                stack.append((x + dx, y + dy))
    cnt = 0
    for i in range(n):
        if vis[i][0]:
            cnt += 1
        if vis[i][-1]:
            cnt += 1
    for i in range(m):
        if vis[0][i]:
            cnt += 1
        if vis[-1][i]:
            cnt += 1
    ans = 0
    for i in range(n):
        ans += grid[i].count('.')
    if cnt == 0:
        print(ans)
    else:

        def p(x, y):
            return x * m + y

        def rev(v):
            return divmod(v, m)
        if cnt == 1:
            dis = [[-1] * m for _ in range(n)]
            dq = deque()
            for i in range(n):
                if vis[i][0]:
                    dq.append(p(i, 0))
                if vis[i][-1]:
                    dq.append(p(i, m - 1))
            for j in range(m):
                if vis[0][j]:
                    dq.append(p(0, j))
                if vis[-1][j]:
                    dq.append(p(n - 1, j))
            for v in dq:
                (x, y) = rev(v)
                dis[x][y] = 0
            while dq:
                (x, y) = rev(dq.popleft())
                for (dx, dy) in dirs:
                    if 0 <= x + dx < n and 0 <= y + dy < m and (dis[x + dx][y + dy] == -1) and (grid[x + dx][y + dy] == '.' or grid[x + dx][y + dy] == 'V'):
                        dis[x + dx][y + dy] = dis[x][y] + 1
                        dq.append(p(x + dx, y + dy))
            print(ans - dis[sx][sy])
        else:
            orig_dist = [[-1] * m for _ in range(n)]
            orig_dist[sx][sy] = 0
            dq = deque([(sx, sy)])
            while dq:
                (x, y) = dq.popleft()
                for (dx, dy) in dirs:
                    if 0 <= x + dx < n and 0 <= y + dy < m and (orig_dist[x + dx][y + dy] == -1) and (grid[x + dx][y + dy] == '.'):
                        orig_dist[x + dx][y + dy] = orig_dist[x][y] + 1
                        dq.append((x + dx, y + dy))
            vis = [[-1] * m for _ in range(n)]
            dq = deque()
            for i in range(n):
                if grid[i][0] == '.' or grid[i][0] == 'V':
                    dq.append((p(i, 0), p(i, 0), 0))
                if grid[i][-1] == '.' or grid[i][-1] == 'V':
                    dq.append((p(i, m - 1), p(i, m - 1), 0))
            for j in range(m):
                if grid[0][j] == '.' or grid[0][j] == 'V':
                    dq.append((p(0, j), p(0, j), 0))
                if grid[-1][j] == '.' or grid[-1][j] == 'V':
                    dq.append((p(n - 1, j), p(n - 1, j), 0))
            dis = [[-1] * m for _ in range(n)]
            for val in dq:
                (v, s, d) = val
                (x, y) = rev(v)
                vis[x][y] = v
                dis[x][y] = 0
            res = n * m
            while dq:
                (v, s, d) = dq.popleft()
                (x, y) = rev(v)
                for (dx, dy) in dirs:
                    if 0 <= x + dx < n and 0 <= y + dy < m and (grid[x + dx][y + dy] == '.' or grid[x + dx][y + dy] == 'V') and (vis[x + dx][y + dy] != -2):
                        if vis[x + dx][y + dy] == -1:
                            vis[x + dx][y + dy] = s
                            dis[x + dx][y + dy] = dis[x][y] + 1
                            dq.append((p(x + dx, y + dy), s, d + 1))
                        elif s != vis[x + dx][y + dy] and orig_dist[x + dx][y + dy] != -1:
                            res = min(res, orig_dist[x + dx][y + dy] + d + 1 + dis[x + dx][y + dy])
                            dq.append((p(x + dx, y + dy), s, d + 1))
                            vis[x + dx][y + dy] = -2
            print(ans - res)
    return
t = II()
for _ in range(t):
    main()

Solution (Python):
from sys import *
input = stdin.readline
inputlist = lambda : map(int, stdin.readline().split())
print = lambda n: stdout.write(str(n) + '\n')
printlist = lambda list: stdout.write(' '.join(map(str, list)) + '\n')

def solve():
    (rows, cols) = inputlist()

    def getneighbors(block):
        neighbors = []
        (row, col) = divmod(block, cols)
        if row != 0:
            neighbors.append(block - cols)
        if row != rows - 1:
            neighbors.append(block + cols)
        if col != 0:
            neighbors.append(block - 1)
        if col != cols - 1:
            neighbors.append(block + 1)
        return neighbors
    board = [None] * (rows * cols)
    unblocked = 0
    exits = []
    start = None
    for i in range(rows):
        temp = input().strip()
        for j in range(cols):
            if temp[j] != '#':
                index = cols * i + j
                board[index] = 0
                unblocked += 1
                if temp[j] == 'V':
                    start = index
    for i in range(cols):
        if board[i] is not None:
            exits.append(i)
        if board[i + cols * (rows - 1)] is not None:
            exits.append(i + cols * (rows - 1))
    for i in range(rows):
        if board[cols * i] is not None:
            exits.append(cols * i)
        if board[cols * (i + 1) - 1] is not None:
            exits.append(cols * (i + 1) - 1)
    if len(exits) == 0:
        return unblocked - 1
    distances = [None] * (rows * cols)
    board[start] = 1
    current = [start]
    distance = 0
    while current:
        newcurrent = []
        for block in current:
            distances[block] = distance
            for neighbor in getneighbors(block):
                if board[neighbor] == 0:
                    board[neighbor] = 1
                    newcurrent.append(neighbor)
        current = newcurrent
        distance += 1
    realexits = [exit for exit in exits if board[exit] == 1]
    if len(realexits) <= 1:
        return unblocked - 1 - distances[realexits[0]] if realexits else unblocked - 1
    sumdistances = [None] * (rows * cols)
    sourcearray = [None] * (rows * cols)
    current = [(10 ** 8 + 1) * i for i in realexits]
    for block in realexits:
        sumdistances[block] = 0
        sourcearray[block] = block
    distance = 1
    minimum = float('inf')
    while current and distance < minimum:
        newcurrent = set()
        for number in current:
            (block, source) = divmod(number, 10 ** 8)
            for neighbor in getneighbors(block):
                if board[neighbor] == 1 and sourcearray[neighbor] != source:
                    newcurrent.add(neighbor * 10 ** 8 + source)
                    if sumdistances[neighbor] is None:
                        sumdistances[neighbor] = distance
                        sourcearray[neighbor] = source
                    else:
                        sumdistances[neighbor] += distance
                        minimum = min(minimum, sumdistances[neighbor] + distances[neighbor])
                        board[neighbor] = 2
        current = newcurrent
        distance += 1
    return unblocked - minimum - 1
for _ in range(int(input())):
    print(solve())