Row Bombing Codechef Solution

Problem

There is an $N\times M$ grid, with rows numbered $1$ to $N$ from top to bottom, and columns $1$ to $M$ from left to right.

Chef starts at cell $(1,1)$ and wants to reach cell $(N,M)$. However, some cells contain walls. Chef can move from their current cell to any adjacent cell (a cell which shares an edge) within the grid that does not contain a wall. So it may be possible initially that all of Chef’s paths to $(N,M)$ are blocked by walls.

To get around this, Chef can call an airstrike on any row and annihilate all walls present in that row. More formally, if Chef chooses row $i$ $(1\le i\le N)$, then any walls in cells $(i,1),(i,2)\dots (i,M)$ are destroyed. Once a wall is destroyed, the cell becomes freely passable.

Since airstrikes are expensive, help Chef find the minimum number of airstrikes Chef must call to guarantee that Chef can reach $(N,M)$ from $(1,1)$.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers $N$ and $M$ — the number of rows and the number of columns in the grid.
• The next $N$ lines contain $M$ characters each, describing the grid. The character at the $i$-th row and $j$-th column S_{i, j}Si,j​ is $\text{’.’}$ if the cell $(i,j)$ is empty and $\text{’\#’}$ if there is a wall.

Output Format

For each test case, output on a new line the minimum number of airstrikes Chef must call to guarantee that Chef can reach $(N,M)$ from $(1,1)$.

Constraints

Sample 1:

5
1 2
..
1 4
.##.
4 1
.
#
#
.
3 2
.#
##
##
3 3
.##
#.#
##.

0
1
2
2
1

Explanation:

Test case 1:
Chef does not need to call any airstrikes. Chef can follow the path $(1,1)\to (1,2)$.

Test case 2:
Chef must call an airstrike on row $1$. This will destroy the walls at $(1,2)$ and $(1,3)$. Chef can then follow the path $(1,1)\to (1,2)\to (1,3)\to (1,4)$.

Test case 3:
Chef must call airstrikes on rows $2$ and $3$. This will destroy the walls at $(2,1)$ and $(3,1)$ respectively. Chef can then follow the path $(1,1)\to (2,1)\to (3,1)\to (4,1)$.