Geek is in a maze of size N * M. 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 = 3, M = 4
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( If he is standing on obstacle he can not move). 
Constraints:
1 ≤ N*M ≤ 10^{6}
mat[i][j] = '#" or '.'
0 ≤ R ≤ N-1
0 ≤ C ≤ M-1

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

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

        # code here

Solutions:
import heapq as hq

class Solution:

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

	def numberOfCells(self, 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 self.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 self.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 self.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 self.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


from collections import deque

class Solution:

	def helper(self, x, y, n, m, u, d, count, mat):
		q = deque()
		q.append([x, y, u, d])
		while q:
			(x, y, u, d) = q.popleft()
			if -1 < y - 1 and mat[x][y - 1] == '.':
				mat[x][y - 1] = '#'
				self.count += 1
				q.append([x, y - 1, u, d])
			if y + 1 < m and mat[x][y + 1] == '.':
				mat[x][y + 1] = '#'
				self.count += 1
				q.append([x, y + 1, u, d])
			if -1 < x - 1 and mat[x - 1][y] == '.' and (u > 0):
				mat[x - 1][y] = '#'
				self.count += 1
				q.append([x - 1, y, u - 1, d])
			if x + 1 < n and mat[x + 1][y] == '.' and (d > 0):
				mat[x + 1][y] = '#'
				self.count += 1
				q.append([x + 1, y, u, d - 1])

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


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, l):
		if r >= n or r < 0 or c >= m or (c < 0) or (l[r][c] == '#'):
			return 0
		diff = [[0, -1], [0, 1], [1, 0], [-1, 0]]
		ans = 1
		l[r][c] = '#'
		q = [[r, c, 0, 0]]
		while q:
			(i, j, a, b) = q.pop(0)
			for (di, dj) in diff:
				ni = i + di
				nj = j + dj
				if ni >= 0 and nj >= 0 and (ni < n) and (nj < m) and (l[ni][nj] == '.'):
					if di < 0 and a + 1 > u:
						continue
					elif di > 0 and b + 1 > d:
						continue
					else:
						l[ni][nj] = '#'
						ans += 1
						if di < 0:
							q.append([ni, nj, a + 1, b])
						elif di > 0:
							q.append([ni, nj, a, b + 1])
						else:
							q.append([ni, nj, a, b])
		return ans


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		marked = [[0 for _ in range(m)] for _ in range(n)]
		marked[r][c] = 1
		q = deque()
		q.append(r)
		q.append(c)
		q.append(u)
		q.append(d)
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		ans = 0
		while len(q):
			x = q.popleft()
			y = q.popleft()
			cu = q.popleft()
			cd = q.popleft()
			ans += 1
			for i in range(4):
				nx = x + dx[i]
				ny = y + dy[i]
				if not (nx >= 0 and nx < n and (ny >= 0) and (ny < m)):
					continue
				if mat[nx][ny] == '#' or marked[nx][ny] == 1:
					continue
				if i == 2 and cu == 0:
					continue
				if i == 3 and cd == 0:
					continue
				marked[nx][ny] = 1
				q.append(nx)
				q.append(ny)
				if i == 2:
					q.append(cu - 1)
				else:
					q.append(cu)
				if i == 3:
					q.append(cd - 1)
				else:
					q.append(cd)
		return ans


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, up, do, mat):
		if mat[r][c] == '#':
			return 0
		que = deque()
		visited = [[0] * m for i in range(n)]
		visited[r][c] = True
		ans = 1
		que.append((r, c, 0, 0))
		while que:
			v = que.popleft()
			x = v[0]
			y = v[1]
			u = v[2]
			d = v[3]
			if y - 1 >= 0 and (not visited[x][y - 1]) and (mat[x][y - 1] == '.'):
				que.append((x, y - 1, u, d))
				visited[x][y - 1] = True
				ans += 1
			if y + 1 < m and (not visited[x][y + 1]) and (mat[x][y + 1] == '.'):
				que.append((x, y + 1, u, d))
				visited[x][y + 1] = True
				ans += 1
			if x - 1 >= 0 and (not visited[x - 1][y]) and (mat[x - 1][y] == '.') and (u < up):
				que.append((x - 1, y, u + 1, d))
				visited[x - 1][y] = True
				ans += 1
			if x + 1 < n and (not visited[x + 1][y]) and (mat[x + 1][y] == '.') and (d < do):
				que.append((x + 1, y, u, d + 1))
				visited[x + 1][y] = True
				ans += 1
		return ans


class Solution:

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


class Solution:

	def numberOfCells(self, 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


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		cnt = 0
		queue = []
		mat[r][c] = '#'
		queue.append([r, c, u, d])
		while len(queue) != 0:
			p = queue.pop(0)
			cnt += 1
			x = p[0]
			y = p[1]
			uu = p[2]
			dd = p[3]
			i = x
			j = y - 1
			if 0 <= j and mat[i][j] == '.':
				mat[i][j] = '#'
				queue.append([i, j, uu, dd])
			i = x
			j = y + 1
			if j < m and mat[i][j] == '.':
				mat[i][j] = '#'
				queue.append([i, j, uu, dd])
			i = x - 1
			j = y
			if 0 <= i and mat[i][j] == '.' and uu:
				mat[i][j] = '#'
				queue.append([i, j, uu - 1, dd])
			i = x + 1
			j = y
			if i < n and mat[i][j] == '.' and dd:
				mat[i][j] = '#'
				queue.append([i, j, uu, dd - 1])
		return cnt


class Solution:

	def numberOfCells(self, 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


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		(m, n) = (n, m)
		visited = [[False for i in range(n)] for j in range(m)]
		count = [1]
		a = [0, 0, -1, 1]
		b = [-1, 1, 0, 0]

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


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		if mat[r][c] == '#':
			return 0
		q = deque()
		q.append((r, c, u, d))
		count = 0
		mat[r][c] = '#'
		while q:
			(r, c, u, d) = q.popleft()
			count += 1
			i = r
			j = c - 1
			if j >= 0 and mat[i][j] == '.':
				mat[i][j] = '#'
				q.append((i, j, u, d))
			i = r
			j = c + 1
			if j < m and mat[i][j] == '.':
				mat[i][j] = '#'
				q.append((i, j, u, d))
			i = r - 1
			j = c
			if i >= 0 and u > 0 and (mat[i][j] == '.'):
				mat[i][j] = '#'
				q.append((i, j, u - 1, d))
			i = r + 1
			j = c
			if i < n and d > 0 and (mat[i][j] == '.'):
				mat[i][j] = '#'
				q.append((i, j, u, d - 1))
		return count


class Solution:

	def numberOfCells(self, n, m, i, j, u, d, mat):
		count = 0
		queue = []
		if self.isValid(n, m, i, j) == True and mat[i][j] == '.':
			mat[i][j] = '#'
			queue.append((i, j, u, d))
			while len(queue) > 0:
				(i0, j0, upCount, downCount) = queue.pop(0)
				count += 1
				for (pos_i, pos_j) in [(i0, j0 - 1), (i0, j0 + 1), (i0 - 1, j0), (i0 + 1, j0)]:
					if self.isValid(n, m, pos_i, pos_j) == True and mat[pos_i][pos_j] == '.':
						if pos_i == i0:
							queue.append((pos_i, pos_j, upCount, downCount))
							mat[pos_i][pos_j] = '#'
						elif pos_i == i0 - 1 and upCount > 0:
							queue.append((pos_i, pos_j, upCount - 1, downCount))
							mat[pos_i][pos_j] = '#'
						elif pos_i == i0 + 1 and downCount > 0:
							queue.append((pos_i, pos_j, upCount, downCount - 1))
							mat[pos_i][pos_j] = '#'
						else:
							pass
		return count

	def isValid(self, n, m, i, j):
		if i < n and i >= 0 and (j < m) and (j >= 0):
			return True
		else:
			return False


from collections import deque

class Solution:

	def recur(self, r, c, u, d):
		q = deque([(r, c, u, d)])
		(n, m, mat) = (self.n, self.m, self.mat)
		mat[r][c] = (u, d)
		self.ans += 1
		while q:
			(r, c, u, d) = q.popleft()
			for (nr, nc) in ((r, c - 1), (r, c + 1)):
				if 0 <= nc < m:
					v = mat[nr][nc]
					if v == '.' or (v != '#' and (v[0] < u or v[1] < d)):
						self.ans += 1 if v == '.' else 0
						q.append((nr, nc, u, d))
						mat[nr][nc] = (u, d)
			nr = r - 1
			if 0 <= nr < n and u > 0:
				v = mat[nr][c]
				if v == '.' or (v != '#' and (v[0] < u - 1 or v[1] < d)):
					self.ans += 1 if v == '.' else 0
					q.append((nr, c, u - 1, d))
					mat[nr][c] = (u - 1, d)
			nr = r + 1
			if 0 <= nr < n and d > 0:
				v = mat[nr][c]
				if v == '.' or (v != '#' and (v[0] < u or v[1] < d - 1)):
					self.ans += 1 if v == '.' else 0
					q.append((nr, c, u, d - 1))
					mat[nr][c] = (u, d - 1)

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


import collections

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		queue = collections.deque([])
		if mat[r][c] == '#':
			return 0
		queue.append((r, c, u, d))
		mask = [(0, -1), (0, 1), (-1, 0), (1, 0)]
		count = 0
		while queue:
			(i, j, up, down) = queue.popleft()
			if mat[i][j] == '.':
				count += 1
				mat[i][j] = '#'
				for (x, y) in mask:
					x_n = i + x
					y_n = j + y
					up_n = up
					down_n = down
					if x == 1:
						down_n -= 1
						if down_n < 0:
							continue
					if x == -1:
						up_n -= 1
						if up_n < 0:
							continue
					if 0 <= x_n < n and 0 <= y_n < m and (mat[x_n][y_n] == '.'):
						queue.append((x_n, y_n, up_n, down_n))
		return count


class Solution:

	def is_valid(self, i, j, r, c, mat, visited):
		if i < 0 or i >= r or j < 0 or (j >= c):
			return 0
		return mat[i][j] == '.' and (not visited[i][j])

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		visited = [[False for j in range(m)] for i in range(n)]
		q = [[r, c, u, d]]
		ans = 0
		visited[r][c] = True
		while q:
			(x, y, u, d) = q.pop(0)
			if self.is_valid(x, y - 1, n, m, mat, visited):
				q.append([x, y - 1, u, d])
				visited[x][y - 1] = True
				ans += 1
			if self.is_valid(x, y + 1, n, m, mat, visited):
				q.append([x, y + 1, u, d])
				visited[x][y + 1] = True
				ans += 1
			if self.is_valid(x - 1, y, n, m, mat, visited):
				if u:
					q.append([x - 1, y, u - 1, d])
					visited[x - 1][y] = True
					ans += 1
			if self.is_valid(x + 1, y, n, m, mat, visited):
				if d:
					q.append([x + 1, y, u, d - 1])
					visited[x + 1][y] = True
					ans += 1
		return ans + 1


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		visited = [[0 for _ in range(m)] for _ in range(n)]
		visited[r][c] = 1
		q = []
		q.append([r, c, u, d])
		cnt = 0
		while q:
			(x, y, U, D) = q.pop(0)
			if y - 1 >= 0 and visited[x][y - 1] == 0 and (mat[x][y - 1] == '.'):
				visited[x][y - 1] = 1
				q.append([x, y - 1, U, D])
			if y + 1 < m and visited[x][y + 1] == 0 and (mat[x][y + 1] == '.'):
				visited[x][y + 1] = 1
				q.append([x, y + 1, U, D])
			if x - 1 >= 0 and U - 1 >= 0 and (visited[x - 1][y] == 0) and (mat[x - 1][y] == '.'):
				visited[x - 1][y] = 1
				q.append([x - 1, y, U - 1, D])
			if x + 1 < n and D - 1 >= 0 and (visited[x + 1][y] == 0) and (mat[x + 1][y] == '.'):
				visited[x + 1][y] = 1
				q.append([x + 1, y, U, D - 1])
		for i in range(n):
			for j in range(m):
				if visited[i][j] == 1:
					cnt += 1
		return cnt


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] != '.':
			return 0
		visit = {(r, c)}
		coordi = [(r, c, u, d)]

		def helper(r, c):
			if r >= 0 and r < n and (c >= 0) and (c < m) and ((r, c) not in visit) and (mat[r][c] == '.'):
				visit.add((r, c))
				return True
			return False
		while coordi:
			coordi2 = []
			while coordi:
				(i, j, up, down) = coordi.pop()
				if helper(i, j - 1):
					coordi.append((i, j - 1, up, down))
				if helper(i, j + 1):
					coordi.append((i, j + 1, up, down))
				if up > 0 and helper(i - 1, j):
					coordi2.append((i - 1, j, up - 1, down))
				if down > 0 and helper(i + 1, j):
					coordi2.append((i + 1, j, up, down - 1))
			coordi = coordi2
		return len(visit)


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		count = 1
		stack = deque()
		stack.append([r, c, 0, 0])
		mat[r][c] = '1'
		while stack:
			row = stack[0][0]
			col = stack[0][1]
			up = stack[0][2]
			down = stack[0][3]
			stack.popleft()
			if col - 1 >= 0 and mat[row][col - 1] == '.':
				count += 1
				stack.append([row, col - 1, up, down])
				mat[row][col - 1] = '1'
			if col + 1 < m and mat[row][col + 1] == '.':
				count += 1
				stack.append([row, col + 1, up, down])
				mat[row][col + 1] = '1'
			if row - 1 >= 0 and up < u and (mat[row - 1][col] == '.'):
				count += 1
				stack.append([row - 1, col, up + 1, down])
				mat[row - 1][col] = '1'
			if row + 1 < n and down < d and (mat[row + 1][col] == '.'):
				count += 1
				stack.append([row + 1, col, up, down + 1])
				mat[row + 1][col] = '1'
		return count


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		to_visit = []
		ptr = 0
		to_visit.append((r, c, 0, 0))
		res = 0
		if mat[r][c] != '#':
			res += 1
			mat[r][c] = '#'
		else:
			return 0
		while ptr < len(to_visit):
			(x, y, up_limit, down_limit) = to_visit[ptr]
			ptr += 1
			if y > 0 and mat[x][y - 1] == '.':
				res += 1
				mat[x][y - 1] = '#'
				to_visit.append((x, y - 1, up_limit, down_limit))
			if y < m - 1 and mat[x][y + 1] == '.':
				res += 1
				mat[x][y + 1] = '#'
				to_visit.append((x, y + 1, up_limit, down_limit))
			if up_limit < u and x > 0 and (mat[x - 1][y] == '.'):
				res += 1
				mat[x - 1][y] = '#'
				to_visit.append((x - 1, y, up_limit + 1, down_limit))
			if down_limit < d and x < n - 1 and (mat[x + 1][y] == '.'):
				res += 1
				mat[x + 1][y] = '#'
				to_visit.append((x + 1, y, up_limit, down_limit + 1))
		return res


class Solution:

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

		def isValid(i, j, up, down):
			if i < 0 or j < 0 or i >= n or (j >= m) or (mat[i][j] == '#') or ((i, j) in visited):
				return False
			if up > u or down > d:
				return False
			return True
		answer = 1
		q = []
		q.append((r, c, 0, 0))
		visited.add((r, c))
		dx = [0, 1, -1, 0]
		dy = [-1, 0, 0, 1]
		dd = [0, 1, 0, 0]
		du = [0, 0, 1, 0]
		while q:
			(row, col, up, down) = q.pop(0)
			for i in range(4):
				newRow = row + dx[i]
				newCol = col + dy[i]
				newUp = up + du[i]
				newDown = down + dd[i]
				if isValid(newRow, newCol, newUp, newDown):
					answer += 1
					visited.add((newRow, newCol))
					q.append((newRow, newCol, newUp, newDown))
		return answer


import queue

class Solution:

	def check_index(self, i, j, n, m, mat, visited):
		if i < 0 or j < 0 or i > n - 1 or (j > m - 1) or ((i, j) in visited) or (mat[i][j] == '#'):
			return False
		visited.add((i, j))
		return True

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		q = queue.deque()
		visited = {(r, c)}
		q.append((r, c, u, d))
		while q:
			q2 = queue.deque()
			while q:
				(i, j, u, d) = q.popleft()
				if self.check_index(i, j + 1, n, m, mat, visited):
					q.append((i, j + 1, u, d))
				if self.check_index(i, j - 1, n, m, mat, visited):
					q.append((i, j - 1, u, d))
				if u > 0 and self.check_index(i - 1, j, n, m, mat, visited):
					q2.append((i - 1, j, u - 1, d))
				if d > 0 and self.check_index(i + 1, j, n, m, mat, visited):
					q2.append((i + 1, j, u, d - 1))
			q = q2.copy()
		return len(visited)


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] != '.':
			return 0
		visited = {(r, c)}
		coord = [(r, c, u, d)]

		def check(row, col):
			if row >= 0 and row < n and (col >= 0) and (col < m) and ((row, col) not in visited) and (mat[row][col] == '.'):
				visited.add((row, col))
				return True
			return False
		while coord:
			coord2 = []
			while coord:
				(i, j, up, down) = coord.pop()
				if check(i, j - 1):
					coord.append((i, j - 1, up, down))
				if check(i, j + 1):
					coord.append((i, j + 1, up, down))
				if up > 0 and check(i - 1, j):
					coord2.append((i - 1, j, up - 1, down))
				if down > 0 and check(i + 1, j):
					coord2.append((i + 1, j, up, down - 1))
			coord = coord2
		return len(visited)


from collections import deque

class Solution:

	def numberOfCells(self, rows, cols, r, c, u, d, mat):
		visited = [[False for _ in range(cols)] for _ in range(rows)]
		queue = deque()
		if mat[r][c] == '#':
			return 0
		queue.append((r, c, 0, 0))
		mat[r][c] = '1'
		dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
		while queue:
			(x, y, up, down) = queue.popleft()
			if y > 0 and mat[x][y - 1] == '.':
				queue.append((x, y - 1, up, down))
				mat[x][y - 1] = '1'
			if y < cols - 1 and mat[x][y + 1] == '.':
				queue.append((x, y + 1, up, down))
				mat[x][y + 1] = '1'
			if x > 0 and up != u and (mat[x - 1][y] == '.'):
				queue.append((x - 1, y, up + 1, down))
				mat[x - 1][y] = '1'
			if x < rows - 1 and down != d and (mat[x + 1][y] == '.'):
				queue.append((x + 1, y, up, down + 1))
				mat[x + 1][y] = '1'
		count = 0
		for i in range(rows):
			for j in range(cols):
				if mat[i][j] == '1':
					count += 1
		return count


class Solution:

	def isValid(self, x, y, n, m, up, do, graph, vis):
		if x < 0 or x >= n or up < 0 or (do < 0) or (y < 0) or (y >= m) or (graph[x][y] == '#') or (vis[x][y] == 1):
			return False
		return True

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		vis = [[0] * m for _ in range(n)]
		qu = []
		qu.append((r, c, u, d))
		vis[r][c] = 1
		cnt = 1
		while len(qu):
			x = qu.pop(0)
			r = x[0]
			c = x[1]
			up = x[2]
			do = x[3]
			if self.isValid(r, c - 1, n, m, up, do, mat, vis):
				cnt += 1
				vis[r][c - 1] = 1
				qu.append((r, c - 1, up, do))
			if self.isValid(r, c + 1, n, m, up, do, mat, vis):
				cnt += 1
				vis[r][c + 1] = 1
				qu.append((r, c + 1, up, do))
			if self.isValid(r - 1, c, n, m, up - 1, do, mat, vis):
				cnt += 1
				vis[r - 1][c] = 1
				qu.append((r - 1, c, up - 1, do))
			if self.isValid(r + 1, c, n, m, up, do - 1, mat, vis):
				cnt += 1
				vis[r + 1][c] = 1
				qu.append((r + 1, c, up, do - 1))
		return cnt


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] == '#':
			return 0
		qu = []
		qu.append((r, c, u, d))
		mat[r][c] = '#'
		cnt = 1
		while len(qu):
			x = qu.pop(0)
			r = x[0]
			c = x[1]
			up = x[2]
			do = x[3]
			if c - 1 >= 0 and mat[r][c - 1] == '.':
				cnt += 1
				mat[r][c - 1] = '#'
				qu.append((r, c - 1, up, do))
			if c + 1 < m and mat[r][c + 1] == '.':
				cnt += 1
				mat[r][c + 1] = '#'
				qu.append((r, c + 1, up, do))
			if r - 1 >= 0 and mat[r - 1][c] == '.' and (up > 0):
				cnt += 1
				mat[r - 1][c] = '#'
				qu.append((r - 1, c, up - 1, do))
			if r + 1 < n and mat[r + 1][c] == '.' and (do > 0):
				cnt += 1
				mat[r + 1][c] = '#'
				qu.append((r + 1, c, up, do - 1))
		return cnt


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		from collections import deque
		vis = [[False for i in range(m)] for j in range(n)]
		q = deque()
		q.append((r, c, u, d))
		ans = 0
		while q:
			(x, y, uco, dco) = q.popleft()
			if not vis[x][y] and mat[x][y] != '#':
				vis[x][y] = True
				ans += 1
				if y + 1 < m and (not vis[x][y + 1]) and (mat[x][y + 1] != '#'):
					q.append((x, y + 1, uco, dco))
				if y - 1 > -1 and (not vis[x][y - 1]) and (mat[x][y - 1] != '#'):
					q.append((x, y - 1, uco, dco))
				if x - 1 > -1 and (not vis[x - 1][y]) and (mat[x - 1][y] != '#') and (uco - 1 > -1):
					q.append((x - 1, y, uco - 1, dco))
				if x + 1 < n and (not vis[x + 1][y]) and (mat[x + 1][y] != '#') and (dco - 1 > -1):
					q.append((x + 1, y, uco, dco - 1))
		return ans


from collections import deque

class Solution:

	def numberOfCells(self, 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 = deque()
		q.append((r, c, u, d))
		while q:
			(y, x, up, down) = q.popleft()
			if x - 1 >= 0 and mat[y][x - 1] == '.' and (not visited[y][x - 1]):
				res += 1
				visited[y][x - 1] = True
				q.append((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.append((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.append((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.append((y + 1, x, up, down - 1))
		return res


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		q = deque()
		q.append([r, c, 0, 0])
		ans = 0
		vis = set()
		vis.add((r, c))
		if mat[r][c] == '#':
			return 0
		while q:
			ans += 1
			(x, y, up, down) = q.popleft()
			for (a, b) in [[0, -1], [0, 1]]:
				if x + a >= 0 and x + a < n and (y + b >= 0) and (y + b < m) and (mat[x + a][y + b] != '#') and ((x + a, y + b) not in vis):
					q.append([x + a, y + b, up, down])
					vis.add((x + a, y + b))
			if x + 1 < n and down < d and (mat[x + 1][y] != '#') and ((x + 1, y) not in vis):
				q.append([x + 1, y, up, down + 1])
				vis.add((x + 1, y))
			if x - 1 >= 0 and up < u and (mat[x - 1][y] != '#') and ((x - 1, y) not in vis):
				q.append([x - 1, y, up + 1, down])
				vis.add((x - 1, y))
		return ans


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		if mat[r][c] != '.':
			return 0
		visited = [[False for i in range(m)] for j in range(n)]
		q = deque()
		q.append([r, c, u, d])
		visited = {(r, c)}

		def issafe(row, col):
			if row >= 0 and row < n and (col >= 0) and (col < m) and ((row, col) not in visited) and (mat[row][col] == '.'):
				visited.add((row, col))
				return True
			return False
		while q:
			size = len(q)
			while size:
				ele = q.popleft()
				i = ele[0]
				j = ele[1]
				up = ele[2]
				down = ele[3]
				if issafe(i, j - 1):
					q.append([i, j - 1, up, down])
				if issafe(i, j + 1):
					q.append([i, j + 1, up, down])
				if up > 0 and issafe(i - 1, j):
					q.append([i - 1, j, up - 1, down])
				if down > 0 and issafe(i + 1, j):
					q.append([i + 1, j, up, down - 1])
				size -= 1
		return len(visited)


class Solution:

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

		def check(row, col):
			if 0 <= row < n and 0 <= col < m and ((row, col) not in v) and (mat[row][col] == '.'):
				v.add((row, col))
				return True
			return False
		while coord:
			l = []
			while coord:
				(i, j, u, d) = coord.pop()
				if check(i, j - 1):
					coord += ((i, j - 1, u, d),)
				if check(i, j + 1):
					coord += ((i, j + 1, u, d),)
				if u > 0 and check(i - 1, j):
					l += ((i - 1, j, u - 1, d),)
				if d > 0 and check(i + 1, j):
					l += ((i + 1, j, u, d - 1),)
			coord = l
		return len(v)


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, grid):
		from collections import deque
		if grid[r][c] == '#':
			return 0
		q = deque()
		q.append((r, c, 0, 0))
		ans = 1
		visited = [[False for j in range(m)] for i in range(n)]
		visited[r][c] = True
		while q:
			(x, y, up, down) = q.popleft()
			if y + 1 < m and (not visited[x][y + 1]) and (grid[x][y + 1] == '.'):
				ans += 1
				visited[x][y + 1] = True
				q.append((x, y + 1, up, down))
			if y - 1 >= 0 and (not visited[x][y - 1]) and (grid[x][y - 1] == '.'):
				ans += 1
				visited[x][y - 1] = True
				q.append((x, y - 1, up, down))
			if x + 1 < n and down != d and (not visited[x + 1][y]) and (grid[x + 1][y] == '.'):
				ans += 1
				visited[x + 1][y] = True
				q.append((x + 1, y, up, down + 1))
			if x - 1 >= 0 and up != u and (not visited[x - 1][y]) and (grid[x - 1][y] == '.'):
				ans += 1
				visited[x - 1][y] = True
				q.append((x - 1, y, up + 1, down))
		return ans


from queue import Queue

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		q = Queue()
		q.put([[r, c], [0, 0]])
		mat[r][c] = '1'
		while not q.empty():
			(a, b) = q.get()
			(row, column) = a
			(up, down) = b
			if column - 1 >= 0 and mat[row][column - 1] != '#' and (mat[row][column - 1] != '1'):
				q.put([[row, column - 1], [up, down]])
				mat[row][column - 1] = '1'
			if column + 1 < m and mat[row][column + 1] != '#' and (mat[row][column + 1] != '1'):
				q.put([[row, column + 1], [up, down]])
				mat[row][column + 1] = '1'
			if row + 1 < n and down != d and (mat[row + 1][column] != '#') and (mat[row + 1][column] != '1'):
				q.put([[row + 1, column], [up, down + 1]])
				mat[row + 1][column] = '1'
			if row - 1 >= 0 and up != u and (mat[row - 1][column] != '#') and (mat[row - 1][column] != '1'):
				q.put([[row - 1, column], [up + 1, down]])
				mat[row - 1][column] = '1'
		ans = 0
		for row in mat:
			ans += row.count('1')
		return ans


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		count = 0
		q = [(r, c, 0, 0)]
		mat[r][c] = '#'
		while q:
			(i, j, uu, dd) = q.pop(0)
			count += 1
			for (x, y) in [(0, +1), (0, -1), (-1, 0), (+1, 0)]:
				(xx, yy) = (i + x, j + y)
				if not (0 <= xx < n and 0 <= yy < m and (mat[xx][yy] == '.')):
					continue
				if x == +1 and dd + 1 <= d:
					q.append((xx, yy, uu, dd + 1))
					mat[xx][yy] = '#'
				elif x == -1 and uu + 1 <= u:
					q.append((xx, yy, uu + 1, dd))
					mat[xx][yy] = '#'
				elif x == 0:
					q.append((xx, yy, uu, dd))
					mat[xx][yy] = '#'
		return count


class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		q = [[r, c, 0, 0]]
		dx = [1, 0 - 1, 0]
		dy = [0, 1, 0, -1]
		counter = 1
		while q:
			temp = q.pop(0)
			temprow = temp[0]
			tempcolumn = temp[1]
			tempupper = temp[2]
			templower = temp[3]
			mat[temprow][tempcolumn] = 'T'
			if tempcolumn + 1 < len(mat[0]):
				if mat[temprow][tempcolumn + 1] == '.':
					q.append([temprow, tempcolumn + 1, tempupper, templower])
					mat[temprow][tempcolumn + 1] = 'T'
					counter += 1
			if tempcolumn - 1 >= 0:
				if mat[temprow][tempcolumn - 1] == '.':
					q.append([temprow, tempcolumn - 1, tempupper, templower])
					mat[temprow][tempcolumn - 1] = 'T'
					counter += 1
			if tempupper < u and temprow - 1 >= 0:
				if mat[temprow - 1][tempcolumn] == '.':
					q.append([temprow - 1, tempcolumn, tempupper + 1, templower])
					mat[temprow - 1][tempcolumn] = 'T'
					counter += 1
			if templower < d and temprow + 1 < len(mat):
				if mat[temprow + 1][tempcolumn] == '.':
					q.append([temprow + 1, tempcolumn, tempupper, templower + 1])
					mat[temprow + 1][tempcolumn] = 'T'
					counter += 1
		return counter


from collections import deque

class Solution:

	def numberOfCells(self, n, m, r, c, u, d, mat):
		mat[r][c] = '.'
		Q = deque([(r, c, u, d)])
		free = sum([mat[i][j] == '.' for i in range(n) for j in range(m)])
		visited = {(r, c, u, d)}
		res = set()
		while Q:
			(x, y, ru, rd) = Q.pop()
			res.add((x, y))
			if len(res) == free:
				break
			if y and mat[x][y - 1] == '.' and ((x, y - 1) not in visited):
				visited.add((x, y - 1))
				Q.appendleft((x, y - 1, ru, rd))
			if y < m - 1 and mat[x][y + 1] == '.' and ((x, y + 1) not in visited):
				visited.add((x, y + 1))
				Q.appendleft((x, y + 1, ru, rd))
			if x and ru and (mat[x - 1][y] == '.') and ((x - 1, y) not in visited):
				visited.add((x - 1, y))
				Q.appendleft((x - 1, y, ru - 1, rd))
			if x < n - 1 and rd and (mat[x + 1][y] == '.') and ((x + 1, y) not in visited):
				visited.add((x + 1, y))
				Q.appendleft((x + 1, y, ru, rd - 1))
		return len(res)