Geek is in a maze of size N * M (N rows, M columns). Each cell in the maze is made of either '.' or '#'. An empty cell is represented by '.' and an obstacle is represented by '#'. If Geek starts at cell (R, C), find how many different empty cells he can pass through while avoiding the obstacles. He can move in any of the four directions but he can move up at most U times and he can move down atmost D times.
 
 
Example 1:
Input: 
N = 3, M = 3
R = 1, C = 0
U = 1, D = 1
mat = {{'.', '.', '.'},
       {'.', '#', '.'},
       {'#', '.', '.'}}
Output: 5
Explanation: Geek can reach 
(1, 0), (0, 0), (0, 1), (0, 2), (1, 2) 
Example 2:
Input: 
N = 4, M = 3
R = 1, C = 0
U = 1, D = 2 
mat = {{'.', '.', '.'}, 
       {'.', '#', '.'}, 
       {'.', '.', '.'},
       {'#', '.', '.'}} 
Output: 10
Explanation: Geek can reach all the 
cells except for the obstacles.
 
Your Task:  
You don't need to read input or print anything. Complete the function numberOfCells() which takes N, M, R, C, U, D and the two dimensional character array mat[][] as input parameters and returns the number of cells geek can visit. 
Constraints:
1 ≤ N*M ≤ 10^{6}
mat[i][j] = '#" or '.'
0 ≤ R ≤ N-1
0 ≤ C ≤ M-1
mat[R][C] = '.'

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3

def numberOfCells(n, m, r, c, u, d, mat):
    # code here

Solutions:
from collections import deque

def numberOfCells(n, m, r, c, u, d, mat):

	def helper(i, j, u, d):
		if j > 0 and (not (i, j - 1) in visited):
			visited.add((i, j - 1))
			helper(i, j - 1, u, d)
		if j < m - 1 and (not (i, j + 1) in visited):
			visited.add((i, j + 1))
			helper(i, j + 1, u, d)
		if u and i > 0 and (not (i - 1, j) in visited):
			visited.add((i - 1, j))
			queue.append((i - 1, j, u - 1, d))
		if d and i < n - 1 and (not (i + 1, j) in visited):
			visited.add((i + 1, j))
			queue.append((i + 1, j, u, d - 1))
	if mat[r][c] == '#':
		return 0
	visited = set()
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '#':
				visited.add((i, j))
	obstacles = len(visited)
	visited.add((r, c))
	queue = deque()
	queue.append((r, c, u, d))
	while queue:
		(a, b, c, d) = queue.popleft()
		helper(a, b, c, d)
	return len(visited) - obstacles


from collections import deque

def numberOfCells(n, m, r, c, u, d, mat):
	if mat[r][c] == '#':
		return 0

	def isvalid(x, y):
		if x < 0 or y < 0 or x >= n or (y >= m) or (mat[x][y] == '#'):
			return False
		return True
	q = deque()
	cnt = 0
	q.append((r, c, u, d))
	visited = [[False for j in range(m)] for i in range(n)]
	visited[r][c] = True
	directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	while q:
		(x, y, up, down) = q.popleft()
		cnt += 1
		if isvalid(x, y - 1) and visited[x][y - 1] == False:
			visited[x][y - 1] = True
			q.append((x, y - 1, up, down))
		if isvalid(x, y + 1) and visited[x][y + 1] == False:
			visited[x][y + 1] = True
			q.append((x, y + 1, up, down))
		if up > 0 and isvalid(x - 1, y) and (visited[x - 1][y] == False):
			visited[x - 1][y] = True
			q.append((x - 1, y, up - 1, down))
		if down > 0 and isvalid(x + 1, y) and (visited[x + 1][y] == False):
			visited[x + 1][y] = True
			q.append((x + 1, y, up, down - 1))
	return cnt


from collections import deque
import heapq as hq

def isValid(row, col, n, m):
	if 0 <= row < n and 0 <= col < m:
		return True

def numberOfCells(n, m, r, c, u, d, mat):
	if mat[r][c] == '#':
		return 0
	pque = []
	vis = [[0 for i in range(m)] for j in range(n)]
	hq.heappush(pque, ((0, 0), (r, c)))
	vis[r][c] = 1
	while pque:
		(up, down) = (pque[0][0][0], pque[0][0][1])
		(x, y) = (pque[0][1][0], pque[0][1][1])
		hq.heappop(pque)
		if isValid(x - 1, y, n, m):
			if up + 1 <= u and (not vis[x - 1][y]) and (down <= d) and (mat[x - 1][y] == '.'):
				hq.heappush(pque, ((up + 1, down), (x - 1, y)))
				vis[x - 1][y] = 1
		if isValid(x + 1, y, n, m):
			if down + 1 <= d and (not vis[x + 1][y]) and (up <= u) and (mat[x + 1][y] == '.'):
				hq.heappush(pque, ((up, down + 1), (x + 1, y)))
				vis[x + 1][y] = 1
		if isValid(x, y - 1, n, m):
			if down <= d and (not vis[x][y - 1]) and (up <= u) and (mat[x][y - 1] == '.'):
				hq.heappush(pque, ((up, down), (x, y - 1)))
				vis[x][y - 1] = 1
		if isValid(x, y + 1, n, m):
			if down <= d and (not vis[x][y + 1]) and (up <= u) and (mat[x][y + 1] == '.'):
				hq.heappush(pque, ((up, down), (x, y + 1)))
				vis[x][y + 1] = 1
	ans = 0
	for i in range(n):
		for j in range(m):
			if vis[i][j] == 1:
				ans += 1
	return ans


def numberOfCells(n, m, r, c, u, d, mat):
	if mat[r][c] == '#':
		return 0
	l1 = [[r, c, u, d]]
	l2 = []
	while len(l1) != 0:
		for i in l1:
			(cr, cc, u, d) = i
			index = cc
			while index < m and mat[cr][index] != '#':
				if mat[cr][index] == 'v':
					break
				mat[cr][index] = 'v'
				if u > 0 and cr - 1 >= 0 and (mat[cr - 1][index] == '.'):
					l2.append([cr - 1, index, u - 1, d])
				if d > 0 and cr + 1 < n and (mat[cr + 1][index] == '.'):
					l2.append([cr + 1, index, u, d - 1])
				index += 1
			index = cc - 1
			while index >= 0 and mat[cr][index] != '#':
				if mat[cr][index] == 'v':
					break
				mat[cr][index] = 'v'
				if u > 0 and cr - 1 >= 0 and (mat[cr - 1][index] == '.'):
					l2.append([cr - 1, index, u - 1, d])
				if d > 0 and cr + 1 < n and (mat[cr + 1][index] == '.'):
					l2.append([cr + 1, index, u, d - 1])
				index -= 1
		l1 = l2[:]
		l2 = []
	ans = 0
	for i in range(n):
		for j in range(m):
			if mat[i][j] == 'v':
				ans += 1
	return ans


def numberOfCells(n, m, r, c, u, d, grid):
	if grid[r][c] == '#':
		return 0
	vis = [[0] * m for i in range(n)]
	q = [[r, c, 0, 0]]
	vis[r][c] = 1
	ans = 1
	while q:
		(x, y, up, down) = q.pop(0)
		if y - 1 >= 0 and (not vis[x][y - 1]) and (grid[x][y - 1] == '.'):
			ans += 1
			vis[x][y - 1] = 1
			q.append([x, y - 1, up, down])
		if y + 1 < m and (not vis[x][y + 1]) and (grid[x][y + 1] == '.'):
			ans += 1
			vis[x][y + 1] = 1
			q.append([x, y + 1, up, down])
		if x + 1 < n and (not vis[x + 1][y]) and (down < d) and (grid[x + 1][y] == '.'):
			ans += 1
			vis[x + 1][y] = 1
			q.append([x + 1, y, up, down + 1])
		if x - 1 >= 0 and (not vis[x - 1][y]) and (up < u) and (grid[x - 1][y] == '.'):
			ans += 1
			vis[x - 1][y] = 1
			q.append([x - 1, y, up + 1, down])
	return ans


def numberOfCells(n, m, r, c, u, d, mat):
	if mat[r][c] == '#':
		return 0
	q = []
	count = 1
	q.append([r, c, 0, 0])
	mat[r][c] = 1
	while q:
		temp = q.pop(0)
		x = temp[0]
		y = temp[1]
		up = temp[2]
		down = temp[3]
		if y - 1 >= 0 and mat[x][y - 1] == '.':
			count += 1
			q.append([x, y - 1, up, down])
			mat[x][y - 1] = 1
		if y + 1 < m and mat[x][y + 1] == '.':
			count += 1
			q.append([x, y + 1, up, down])
			mat[x][y + 1] = 1
		if x - 1 >= 0 and up != u and (mat[x - 1][y] == '.'):
			count += 1
			q.append([x - 1, y, up + 1, down])
			mat[x - 1][y] = 1
		if x + 1 < n and down != d and (mat[x + 1][y] == '.'):
			count += 1
			q.append([x + 1, y, up, down + 1])
			mat[x + 1][y] = 1
	return count


def numberOfCells(n, m, r, c, u, d, mat):
	if mat[r][c] == '#':
		return 0
	q = []
	q.append([r, c, u, d])
	mat[r][c] = 'visited'
	ans = 0
	ans1 = 0
	while len(q) > 0:
		(row, col, up, down) = q.pop(0)
		ans1 += 1
		i = row
		j = col - 1
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.'):
			mat[i][j] = 'Visited'
			q.append([i, j, up, down])
		i = row
		j = col + 1
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.'):
			mat[i][j] = 'Visited'
			q.append([i, j, up, down])
		i = row + 1
		j = col
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.') and down:
			mat[i][j] = 'Visited'
			q.append([i, j, up, down - 1])
		i = row - 1
		j = col
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.') and up:
			mat[i][j] = 'Visited'
			q.append([i, j, up - 1, down])
	return ans1
if __name__ == '__main__':
	t = int(int(input()))
	for tcs in range(t):
		(n, m, r, c, u, d) = [int(x) for x in input().split()]
		mat = []
		for i in range(n):
			matele = [x for x in input()]
			mat.append(matele)
		print(numberOfCells(n, m, r, c, u, d, mat))


def numberOfCells(n, m, r, c, u, d, mat):
	if mat[r][c] == '#':
		return 0
	q = [[r, c, u, d]]
	mat[r][c] = 'Visited'
	res = 0
	while q:
		(row, col, up, down) = q.pop(0)
		res += 1
		i = row
		j = col - 1
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.'):
			mat[i][j] = 'Visited'
			q.append([i, j, up, down])
		i = row
		j = col + 1
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.'):
			mat[i][j] = 'Visited'
			q.append([i, j, up, down])
		i = row + 1
		j = col
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.') and down:
			mat[i][j] = 'Visited'
			q.append([i, j, up, down - 1])
		i = row - 1
		j = col
		if 0 <= i <= n - 1 and 0 <= j <= m - 1 and (mat[i][j] == '.') and up:
			mat[i][j] = 'Visited'
			q.append([i, j, up - 1, down])
	return res


def numberOfCells(n, m, r, c, u, d, mat):
	visited = [[False for i in range(m)] for j in range(n)]

	def possible(i, j, m, n):
		return i >= 0 and j >= 0 and (i < m) and (j < n)

	def solver(t, grid, u, d, m, n):
		(i, j) = (t[0], t[1])
		q = []
		q.append([i, j, u, d])
		while q:
			curr = q.pop(0)
			(i, j, u, d) = curr
			visited[i][j] = True
			a = [0, 0, -1, 1]
			b = [-1, 1, 0, 0]
			for k in range(4):
				(r, c) = (i + a[k], j + b[k])
				if possible(r, c, m, n) and visited[r][c] == False and (grid[r][c] == '.'):
					if k == 2:
						if u > 0:
							q.append([r, c, u - 1, d])
							visited[r][c] = True
					elif k == 3:
						if d > 0:
							q.append([r, c, u, d - 1])
							visited[r][c] = True
					else:
						q.append([r, c, u, d])
						visited[r][c] = True
	if mat[r][c] == '#':
		return 0
	solver([r, c], mat, u, d, n, m)
	count = 0
	for i in range(n):
		for j in range(m):
			if visited[i][j] == True:
				count += 1
	return count


from queue import Queue

def numberOfCells(n, m, r, c, u, d, mat):
	visited = [[False for _ in range(m)] for _ in range(n)]
	if mat[r][c] == '#':
		return 0
	visited[r][c] = True
	res = 1
	q = Queue()
	q.put((r, c, u, d))
	while not q.empty():
		(y, x, up, down) = q.get()
		if x - 1 >= 0 and mat[y][x - 1] == '.' and (not visited[y][x - 1]):
			res += 1
			visited[y][x - 1] = True
			q.put((y, x - 1, up, down))
		if x + 1 < m and mat[y][x + 1] == '.' and (not visited[y][x + 1]):
			res += 1
			visited[y][x + 1] = True
			q.put((y, x + 1, up, down))
		if y - 1 >= 0 and mat[y - 1][x] == '.' and (not visited[y - 1][x]) and (up > 0):
			res += 1
			visited[y - 1][x] = True
			q.put((y - 1, x, up - 1, down))
		if y + 1 < n and mat[y + 1][x] == '.' and (not visited[y + 1][x]) and (down > 0):
			res += 1
			visited[y + 1][x] = True
			q.put((y + 1, x, up, down - 1))
	return res


def BFS(mat, r, c, upM, downM):
	if mat[r][c] == '#':
		return 0
	n = len(mat)
	m = len(mat[0])
	q = [(r, c, upM, downM)]
	count = 0
	visited = [[False for i in range(m)] for j in range(n)]
	visited[r][c] = True
	while len(q):
		(u, v, up, down) = q.pop()
		count = count + 1
		if v + 1 < m:
			if visited[u][v + 1] == False and mat[u][v + 1] != '#':
				visited[u][v + 1] = True
				q.insert(0, (u, v + 1, up, down))
		if v - 1 >= 0:
			if visited[u][v - 1] == False and mat[u][v - 1] != '#':
				visited[u][v - 1] = True
				q.insert(0, (u, v - 1, up, down))
		if up > 0 and u - 1 >= 0:
			if visited[u - 1][v] == False and mat[u - 1][v] != '#':
				visited[u - 1][v] = True
				q.insert(0, (u - 1, v, up - 1, down))
		if down > 0 and u + 1 < n:
			if visited[u + 1][v] == False and mat[u + 1][v] != '#':
				visited[u + 1][v] = True
				q.insert(0, (u + 1, v, up, down - 1))
	return count

def numberOfCells(n, m, r, c, u, d, mat):
	return BFS(mat, r, c, u, d)