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 ≤ i ≤ N), then any walls in cells (i, 1), (i, 2) \ldots (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} is \texttt{'.'} if the cell (i, j) is empty and \texttt{'\#'} 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 ------ 

$1 ≤ T ≤ 2 \cdot 10^{5}$
$2 ≤ N \times M ≤ 5 \cdot 10^{5}$
$S_{i, j} \in \{\texttt{'.'}, \texttt{'\#'}\}$
- The sum of $N \times M$ over all test cases does not exceed $5 \cdot 10^{5}$.
- It is guaranteed that the starting cell $(1, 1)$ is not blocked by a wall.

----- Sample Input 1 ------ 
5
1 2
..
1 4
.##.
4 1
.
#
#
.
3 2
.#
##
##
3 3
.##
#.#
##.

----- Sample Output 1 ------ 
0
1
2
2
1

----- explanation 1 ------ 
Test case 1: 
Chef does not need to call any airstrikes. Chef can follow the path $(1, 1) \rightarrow (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) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (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) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (4, 1)$.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Starter code:

Solutions:
import sys, os, io
input = sys.stdin.readline

def is_valid(x, y):
	if min(x, y) >= 0 and x < n and (y < m) and ((x, y) not in vis) and (a[x][y] != '#'):
		return 1
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = []
	for i in range(n):
		a.append(list(input().strip()))
	vis = set()
	dx = [1, -1, 0, 0]
	dy = [0, 0, 1, -1]
	ans = 0
	depth = 0
	stack = [(0, 0)]
	while len(vis) < n * m:
		while stack:
			(x, y) = stack.pop()
			vis.add((x, y))
			depth = max(depth, x)
			for k in range(4):
				(nx, ny) = (x + dx[k], y + dy[k])
				if is_valid(nx, ny):
					vis.add((nx, ny))
					stack.append((nx, ny))
		if depth != n - 1:
			ans += 1
			for i in range(m):
				a[depth + 1][i] == '.'
				stack.append((depth + 1, i))
		elif (n - 1, m - 1) not in vis:
			ans += 1
			break
		else:
			break
	print(ans)


from itertools import product

class DisJointSets:

	def __init__(self, N):
		self._parents = [node for node in range(N)]
		self._ranks = [1 for _ in range(N)]

	def find(self, u):
		while u != self._parents[u]:
			self._parents[u] = self._parents[self._parents[u]]
			u = self._parents[u]
		return u

	def connected(self, u, v):
		return self.find(u) == self.find(v)

	def union(self, u, v):
		(root_u, root_v) = (self.find(u), self.find(v))
		if root_u == root_v:
			return True
		if self._ranks[root_u] > self._ranks[root_v]:
			self._parents[root_v] = root_u
		elif self._ranks[root_v] > self._ranks[root_u]:
			self._parents[root_u] = root_v
		else:
			self._parents[root_u] = root_v
			self._ranks[root_v] += 1
		return False

def solve():
	(N, M) = map(int, input().split(' '))
	wall = [list(map(lambda x: x == '#', input())) for _ in range(N)]
	striked = set()
	dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

	def biject(r, c):
		pos = M * r + c
		if not 0 <= pos < N * M:
			raise ValueError(r, c, pos, N, M)
		return pos
	ds = DisJointSets(N * M)

	def update_ds(r, c):
		if not (0 <= r < N and 0 <= c < M):
			return
		if r not in striked and wall[r][c]:
			return
		p1 = biject(r, c)
		for (dr, dc) in dirs:
			(nr, nc) = (r + dr, c + dc)
			if not (0 <= nr < N and 0 <= nc < M):
				continue
			if nr not in striked and wall[nr][nc]:
				continue
			p2 = biject(nr, nc)
			ds.union(p1, p2)
	for (r, c) in product(range(N), range(M)):
		update_ds(r, c)
	for r in range(N):
		if any(map(lambda c: ds.connected(biject(0, 0), biject(r, c)), range(M))):
			continue
		striked.add(r)
		for c in range(M):
			update_ds(r, c)
	print(len(striked) if ds.connected(biject(0, 0), biject(N - 1, M - 1)) else len(striked) + 1)
T = int(input())
for _ in range(T):
	solve()


def find(grid, n, m):
	que = []
	que.append([0, 0])
	vis = set()
	l = 0
	dr = [-1, 0, 1, 0]
	dc = [0, 1, 0, -1]
	for score in range(n):
		low = l
		while que:
			(row, col) = que.pop(0)
			vis.add((row, col))
			if row == n - 1 and col == m - 1:
				return score
			for i in range(4):
				nrow = row + dr[i]
				ncol = col + dc[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and ((nrow, ncol) not in vis) and (grid[nrow][ncol] != '#'):
					que.append([nrow, ncol])
					vis.add((nrow, ncol))
					low = max(low, nrow)
		if low == n - 1:
			return score + 1
		l = low + 1
		for i in range(m):
			que.append([low + 1, i])
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = [input() for _ in range(n)]
	print(find(grid, n, m))


def find(g, n, m):
	q = [(0, 0)]
	visited = {0, 0}
	lowest = 0
	for score in range(n):
		low = lowest
		while q:
			(i, j) = q.pop()
			visited.add((i, j))
			if i == n - 1 and j == m - 1:
				return score
			for (a, b) in [(i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)]:
				if lowest <= a < n and 0 <= b < m and ((a, b) not in visited) and (g[a][b] != '#'):
					q.append((a, b))
					visited.add((a, b))
					low = max(low, a)
		if low == n - 1:
			return score + 1
		lowest = low + 1
		q = [(low + 1, i) for i in range(m)]
		visited.update(q)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = [input() for _ in range(n)]
	print(find(g, n, m))


from sys import stdin, setrecursionlimit
input = stdin.readline
inp = lambda : list(map(int, input().split()))
import heapq

def answer():
	dist = [[[float('inf'), float('inf')] for i in range(m)] for j in range(n)]
	dist[0][0] = [0, 0]
	q = []
	heapq.heappush(q, [0, 0, 0, 0])
	while len(q):
		(dis, took, x, y) = heapq.heappop(q)
		if took == 0:
			if x + 1 < n:
				add = a[x + 1][y] == '#'
				if dist[x + 1][y][add] > dist[x][y][0] + add:
					dist[x + 1][y][add] = dist[x][y][0] + add
					heapq.heappush(q, [dist[x + 1][y][add], add, x + 1, y])
			if y + 1 < m:
				add = a[x][y + 1] == '#'
				if dist[x][y + 1][add] > dist[x][y][0] + add:
					dist[x][y + 1][add] = dist[x][y][0] + add
					heapq.heappush(q, [dist[x][y + 1][add], add, x, y + 1])
			if y - 1 >= 0:
				add = a[x][y - 1] == '#'
				if dist[x][y - 1][add] > dist[x][y][0] + add:
					dist[x][y - 1][add] = dist[x][y][0] + add
					heapq.heappush(q, [dist[x][y - 1][add], add, x, y - 1])
			if x - 1 >= 0:
				add = a[x - 1][y] == '#'
				if dist[x - 1][y][add] > dist[x][y][0] + add:
					dist[x - 1][y][add] = dist[x][y][0] + add
					heapq.heappush(q, [dist[x - 1][y][add], add, x - 1, y])
		else:
			if x + 1 < n:
				add = a[x + 1][y] == '#'
				if dist[x + 1][y][add] > dist[x][y][1] + add:
					dist[x + 1][y][add] = dist[x][y][1] + add
					heapq.heappush(q, [dist[x + 1][y][add], add, x + 1, y])
			if y + 1 < m:
				if dist[x][y + 1][1] > dist[x][y][1]:
					dist[x][y + 1][1] = dist[x][y][1]
					heapq.heappush(q, [dist[x][y + 1][1], 1, x, y + 1])
			if x - 1 >= 0:
				add = a[x - 1][y] == '#'
				if dist[x - 1][y][add] > dist[x][y][1] + add:
					dist[x - 1][y][add] = dist[x][y][1] + add
					heapq.heappush(q, [dist[x - 1][y][add], add, x - 1, y])
			if y - 1 >= 0:
				if dist[x][y - 1][1] > dist[x][y][1]:
					dist[x][y - 1][1] = dist[x][y][1]
					heapq.heappush(q, [dist[x][y - 1][1], 1, x, y - 1])
	return min(dist[n - 1][m - 1])
for T in range(int(input())):
	(n, m) = inp()
	a = [input().strip() for i in range(n)]
	print(answer())


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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
find = lambda n, m, l, u: m * l + u + 1
from heapq import heappop, heappush

def dijkstra(graph, start, n):
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)
g = [[] for i in range(2 * 500000 + 2)]
for _ in range(int(input())):
	(n, m) = mi()
	total = n * m
	a = []
	for i in range(n):
		a.append(input())
	for i in range(2 * total + 2):
		g[i].clear()
	for i in range(n):
		for j in range(m):
			if a[i][j] == '.':
				if i > 0:
					x = find(n, m, i, j)
					y = find(n, m, i - 1, j)
					if a[i - 1][j] == '.':
						g[x].append((y, 0))
					g[x].append((total + y, 1))
				if j > 0:
					x = find(n, m, i, j)
					y = find(n, m, i, j - 1)
					if a[i][j - 1] == '.':
						g[x].append((y, 0))
					g[x].append((total + y, 1))
				if i < n - 1:
					x = find(n, m, i, j)
					y = find(n, m, i + 1, j)
					if a[i + 1][j] == '.':
						g[x].append((y, 0))
					g[x].append((total + y, 1))
				if j < m - 1:
					x = find(n, m, i, j)
					y = find(n, m, i, j + 1)
					if a[i][j + 1] == '.':
						g[x].append((y, 0))
					g[x].append((total + y, 1))
			if j > 0:
				g[total + find(n, m, i, j)].append((total + find(n, m, i, j - 1), 0))
				if a[i][j - 1] == '.':
					g[total + find(n, m, i, j)].append((find(n, m, i, j - 1), 0))
			if j < m - 1:
				g[total + find(n, m, i, j)].append((total + find(n, m, i, j + 1), 0))
				if a[i][j + 1] == '.':
					g[total + find(n, m, i, j)].append((find(n, m, i, j + 1), 0))
			if i > 0:
				g[total + find(n, m, i, j)].append((total + find(n, m, i - 1, j), 1))
				if a[i - 1][j] == '.':
					g[total + find(n, m, i, j)].append((find(n, m, i - 1, j), 0))
			if i < n - 1:
				g[total + find(n, m, i, j)].append((total + find(n, m, i + 1, j), 1))
				if a[i + 1][j] == '.':
					g[total + find(n, m, i, j)].append((find(n, m, i + 1, j), 0))
	(res, temp) = dijkstra(g, 1, 2 * total + 2)
	print(min(res[total], res[2 * total]))


import sys
input = sys.stdin.readline
from math import sqrt
from collections import defaultdict, deque

def I():
	return list(map(int, input().split()))
from time import time
st = time()

def bfs():
	max_dep = 0
	stack = [(0, 0)]
	vis = {}
	ans = 0
	while True:
		if time() - st > 1:
			exit()
		while stack:
			if time() - st > 1:
				exit()
			(x, y) = stack.pop()
			max_dep = max(max_dep, x)
			if x == n - 1 and y == m - 1:
				return ans
			for (r, c) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				(X, Y) = (x + r, y + c)
				if 0 <= X < n and 0 <= Y < m and ((X, Y) not in vis) and (mat[X][Y] == '.'):
					stack.append((X, Y))
					vis[X, Y] = True
		if max_dep == n - 1:
			ans += 1
			return ans
		ans += 1
		for j in range(m):
			stack.append((max_dep + 1, j))
for _ in range(int(input())):
	(n, m) = I()
	mat = []
	for i in range(n):
		temp = input().strip()
		mat.append(temp)
	stack = deque([(0, 0)])
	print(bfs())