Вова находится в матрице \(n \times m\). Строки этой матрицы пронумерованы числами от \(1\) до \(n\) сверху вниз, а столбцы пронумерованы числами от \(1\) до \(m\) слева направо. Клетка \((i, j)\) — это клетка на пересечении строки \(i\) и столбца \(j\) для \(1 \leq i \leq n\) и \(1 \leq j \leq m\).
Часть клеток матрицы заблокирована препятствиями (все остальные клетки свободны). Вова находится в одной из свободных клеток. Гарантируется, что клетки \((1, 1)\), \((1, m)\), \((n, 1)\), \((n, m)\) (то есть углы матрицы) заблокированы.
Вова может перейти из одной свободной клетки в другую свободную клетку, если у них есть общая сторона. Вова может выйти из матрицы из любой свободной клетки на границе матрицы, такие клетки называются выходами.
Тип матрицы зависит от количества выходов, которые Вова может использовать, чтобы выйти из матрицы. Существуют матрицы трёх типов:
- \(1\)-го типа: матрицы без выходов, которые Вова может использовать.
- \(2\)-го типа: матрицы ровно с одним выходом, который Вова может использовать, чтобы покинуть матрицу.
- \(3\)-го типа: матрицы с несколькими (двумя или более) выходами, которые Вова может использовать, чтобы покинуть матрицу.
До того как Вова начнёт перемещаться, Миша может создать больше препятствий и заблокировать часть свободных клеток. При этом Миша не может менять тип матрицы. Какое максимальное количество клеток может заблокировать Миша, не изменяя тип матрицы? Миша не может заблокировать клетку, в которой сейчас находится Вова.
Выходные данные
Для каждого набора входных данных выведите одно число: максимальное количество клеток, которые может заблокировать Миша.
Примечание
В первом наборе входных данных дана матрица \(3\)-го типа. Миша может заблокировать все клетки, кроме клеток \((1, 3)\), \((2, 3)\), \((2, 4)\). Существует \(9\) таких клеток и их блокировка не меняет тип матрицы.
Во втором наборе входных данных дана матрица \(3\)-го типа. Блокировка любой клетки меняет тип матрицы на \(2\)-й: один из двух выходов становится недостижимым для Вовы. Поэтому, ответ \(0\).
В третьем наборе входных данных дана матрица \(1\)-го типа. В ней нет свободных клеток (кроме клетки Вовы), поэтому Миша не может заблокировать ни одну клетку.
В четвёртом наборе входных данных дана матрица \(2\)-го типа. Миша может заблокировать \(3\) клетки \((5, 2)\), \((6, 3)\), \((6, 4)\), не изменяя тип матрицы.
В пятом наборе входных данных дана матрица \(3\)-го типа. Миша может заблокировать \(4\) клетки \((2, 2)\), \((3, 2)\), \((4, 2)\), \((5, 2)\) либо \(4\) клетки \((2, 4)\), \((3, 4)\), \((4, 4)\), \((5, 4)\), не изменяя тип матрицы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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##
##.##
#...#
|
9
0
0
3
4
10
12
5
|