Spiderman is stuck in a difficult situation. His arch-enemy the Green Goblin has planted several of his infamous Pumpkin Bombs in various locations in a building. Help Spiderman activate his Spidey Sense and identify the impact zones. 
He has a blueprint of the building which is a M x N matrix that is filled with the characters O, B, and W where: 
O represents an open space.
B represents a bomb.
W represents a wall.
You have to replace all of the Os (open spaces) in the matrix with their shortest distance from a bomb without being able to go through any walls. Also, replace the bombs with 0 and walls with -1 in the resultant matrix. If no path exists between a bomb and an open space replace the corresponding 'O' with -1.
Example 1:
Input: N = 3, M = 3
A[] = {{O, O, O}, 
       {W, B, B}, 
       {W, O, O}}
Output: {{2, 1, 1}, 
         {-1, 0, 0},  
         {-1, 1, 1}}
Explanation: The walls at (1,0) and (2,0) 
are replaced by -1. The bombs at (1,1) and 
(1,2) are replaced by 0. The impact zone 
for the bomb at (1,1) includes open spaces 
at index (0,0), (0,1) and (2,1) with distance 
from bomb calculated as 2,1,1 respectively.
The impact zone for the bomb at (1,2) 
includes open spaces at index (0,3) and (2,2) 
with distance from bomb calculated as 1,1 
respectively.
Example 2:
IInput: N = 2, M = 2
A[] = {{O, O},
       {O, O}} 
Output: {{-1, -1}
         {-1, -1}
Your Task:  
You don't need to read input or print anything. Complete the function findDistance() which takes the matrix A[], M, and N as input parameters and the resultant matrix
Expected Time Complexity: O(M*N)
Expected Auxiliary Space: O(M*N)
Constraints:
1 ≤ N*M ≤ 10^{6}

Difficulty: MEDIUM
Tags: Data structures

Graph algorithms

Graph traversal
Skill types: Data structures
Expected Time Complexity: O(M*N)
Expected Auxiliary Space: O(M*N)

Starter code:


class Solution:

    def findDistance(self, matrix, m, n):

        # Your code goes here







Solutions:
def bfs(tr, tc, grid, dis):
	(n, m) = (len(grid), len(grid[0]))
	visit = [[0] * m for _ in range(n)]
	q = []
	q.append((tr, tc, 0))
	visit[tr][tc] = 1
	while q:
		(r, c, s) = q.pop(0)
		if grid[r][c] == 'B':
			dis[tr][tc] = s
			break
		l = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		for (i, j) in l:
			(nr, nc) = (r + i, c + j)
			if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (grid[nr][nc] != 'W') and (not visit[nr][nc]):
				visit[nr][nc] = 1
				q.append((nr, nc, s + 1))

class Solution:

	def findDistance(self, grid, m, n):
		dis = [[-1] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'O':
					bfs(i, j, grid, dis)
				elif grid[i][j] == 'B':
					dis[i][j] = 0
		return dis


from collections import deque

class Solution:

	def findDistance(self, matrix, n, m):
		ans = [[-1] * m for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 'B':
					ans[i][j] = 0
					q.append((i, j))
		dx = [-1, 0, 0, 1]
		dy = [0, -1, 1, 0]
		while len(q) > 0:
			(x, y) = q.popleft()
			for k in range(4):
				nx = x + dx[k]
				ny = y + dy[k]
				if not (nx >= 0 and nx < n and (ny >= 0) and (ny < m)):
					continue
				if matrix[nx][ny] == 'O' and ans[nx][ny] == -1:
					ans[nx][ny] = ans[x][y] + 1
					q.append((nx, ny))
		return ans


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		q = deque()
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					matrix[i][j] = 0
					q.append((i, j))
				elif matrix[i][j] == 'W':
					matrix[i][j] = -1
		while q:
			size = len(q)
			for i in range(size):
				u = q.popleft()
				for j in range(4):
					x = dx[j] + u[0]
					y = dy[j] + u[1]
					if x >= 0 and y >= 0 and (x < m) and (y < n) and (matrix[x][y] == 'O'):
						q.append((x, y))
						matrix[x][y] = matrix[u[0]][u[1]] + 1
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


import collections

class Solution:

	def findDistance(self, matrix, m, n):
		q = collections.deque([])
		visited = set()
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					q.append((i, j))
					visited.add((i, j))
		level = 0
		di = [1, 0, -1, 0]
		dj = [0, -1, 0, 1]
		while q:
			for k in range(len(q)):
				(i, j) = q.popleft()
				matrix[i][j] = level
				for d in range(4):
					newi = i + di[d]
					newj = j + dj[d]
					if not (0 <= newi < m and 0 <= newj < n):
						continue
					if (newi, newj) in visited or matrix[newi][newj] == 'W':
						continue
					q.append((newi, newj))
					visited.add((newi, newj))
			level += 1
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'W' or matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):

		def issafe(ith, jth):
			if ith >= 0 and ith < len(matrix) and (jth >= 0) and (jth < len(matrix[0])) and (visited[ith][jth] == False) and (matrix[ith][jth] == 'O'):
				return True
			return False
		q = deque()
		visited = [[False for i in range(len(matrix[0]))] for j in range(len(matrix))]
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'W':
					matrix[i][j] = -1
				elif matrix[i][j] == 'B':
					q.append([i, j])
		moves = [[0, 1], [1, 0], [-1, 0], [0, -1]]
		level = -1
		while q:
			size = len(q)
			level += 1
			while size:
				ele = q.popleft()
				if matrix[ele[0]][ele[1]] == 'O':
					matrix[ele[0]][ele[1]] = level
				visited[ele[0]][ele[1]] = True
				if matrix[ele[0]][ele[1]] == 'B':
					matrix[ele[0]][ele[1]] = 0
				for move in moves:
					if issafe(ele[0] + move[0], ele[1] + move[1]):
						q.append([ele[0] + move[0], ele[1] + move[1]])
				size -= 1
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


from collections import deque

class Solution:

	def findDistance(self, matrix, n, m):
		boom = deque()
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 'B':
					boom.append((i, j, 0))
		while boom:
			(i, j, time) = boom.popleft()
			if matrix[i][j] == 'O' or matrix[i][j] == 'B':
				matrix[i][j] = time
			if i < n - 1 and matrix[i + 1][j] == 'O':
				boom.append((i + 1, j, time + 1))
			if i > 0 and matrix[i - 1][j] == 'O':
				boom.append((i - 1, j, time + 1))
			if j < m - 1 and matrix[i][j + 1] == 'O':
				boom.append((i, j + 1, time + 1))
			if j > 0 and matrix[i][j - 1] == 'O':
				boom.append((i, j - 1, time + 1))
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 'W' or matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		que = deque()
		res = [[-1] * n for i in range(m)]
		visited = [[0] * n for i in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					que.append((i, j, 0))
					visited[i][j] = True
					res[i][j] = 0
		x = [0, 0, 1, -1]
		y = [1, -1, 0, 0]

		def isvalid(x, y):
			return x >= 0 and y >= 0 and (x < m) and (y < n) and (not visited[x][y]) and (matrix[x][y] == 'O')
		while que:
			v = que.popleft()
			res[v[0]][v[1]] = v[2]
			for i in range(4):
				if isvalid(v[0] + x[i], v[1] + y[i]):
					que.append((v[0] + x[i], v[1] + y[i], v[2] + 1))
					visited[v[0] + x[i]][v[1] + y[i]] = True
		return res


from collections import deque

class Solution:

	def findDistance(self, mat, m, n):
		a = [[1 << 31 for _ in range(n)] for _ in range(m)]
		q = deque()
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 'B':
					q.append([i, j, 0])
					a[i][j] = 0
				elif mat[i][j] == 'W':
					a[i][j] = -1
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]

		def issafe(x, y):
			return x >= 0 and x < m and (y >= 0) and (y < n)
		while q:
			(curx, cury, d) = q.popleft()
			for k in range(4):
				cx = curx + dx[k]
				cy = cury + dy[k]
				if issafe(cx, cy) and a[cx][cy] == 1 << 31:
					a[cx][cy] = d + 1
					q.append([cx, cy, d + 1])
		for i in range(m):
			for j in range(n):
				if a[i][j] == 1 << 31:
					a[i][j] = -1
		return a


class Solution:

	def findDistance(self, matrix, m, n):
		l1 = []
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					l1.append([i, j])
		l2 = []
		dr = [1, -1, 0, 0]
		dc = [0, 0, -1, 1]
		steps = 1
		while len(l1) != 0:
			for i in l1:
				(cr, cc) = i
				for j in range(4):
					nr = cr + dr[j]
					nc = cc + dc[j]
					if nr >= 0 and nr < m and (nc >= 0) and (nc < n):
						if matrix[nr][nc] == 'O':
							matrix[nr][nc] = steps
							l2.append([nr, nc])
			l1 = l2[:]
			l2 = []
			steps += 1
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					matrix[i][j] = 0
				if matrix[i][j] == 'W' or matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


class Solution:

	def findDistance(self, x, m, n):
		q = []
		(m, n) = (len(x), len(x[0]))
		for i in range(m):
			for j in range(n):
				if x[i][j] == 'B':
					q.append((i, j, 0))
					x[i][j] = 0
				elif x[i][j] == 'W':
					x[i][j] = -1
		while q:
			(i, j, k) = q.pop(0)
			for (d, e) in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
				if 0 <= d < m and 0 <= e < n and (x[d][e] == 'O'):
					x[d][e] = k + 1
					q.append((d, e, k + 1))
		for i in range(m):
			for j in range(n):
				if x[i][j] == 'O':
					x[i][j] = -1
		return x


from collections import deque
import math

class Solution:

	def findDistance(self, matrix, m, n):
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		queue = deque()
		res = [[-1] * n for _ in range(m)]
		for row in range(m):
			for col in range(n):
				if matrix[row][col] == 'B':
					res[row][col] = 0
					queue.append((row, col))
				if matrix[row][col] == 'O':
					res[row][col] = -2
		dist = 0
		while queue:
			count = len(queue)
			while count:
				(x, y) = queue.popleft()
				for d in range(4):
					(nx, ny) = (x + dx[d], y + dy[d])
					if 0 <= nx < m and 0 <= ny < n and (res[nx][ny] == -2):
						res[nx][ny] = dist + 1
						queue.append((nx, ny))
				count -= 1
			dist += 1
		for row in range(m):
			for col in range(n):
				if res[row][col] == -2:
					res[row][col] = -1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		size = input().strip().split()
		m = int(size[0])
		n = int(size[1])
		matrix = []
		for _ in range(m):
			matrix.append([x for x in input().strip().split()])
		obj = Solution()
		result = obj.findDistance(matrix, m, n)
		for i in result:
			for j in i:
				print(j, end=' ')
			print()


from collections import deque

class Solution:

	def findDistance(self, matrix, n, m):
		q = deque()
		res = [[10 ** 9 + 7 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 'B':
					res[i][j] = 0
					q.append((i, j))
				elif matrix[i][j] == 'W':
					res[i][j] = -1
		dx = [0, 1, 0, -1]
		dy = [1, 0, -1, 0]
		while q:
			(i, j) = q.popleft()
			for k in range(4):
				a = i + dx[k]
				b = j + dy[k]
				if a >= 0 and b >= 0 and (a < n) and (b < m) and (matrix[a][b] == 'O') and (res[a][b] > res[i][j] + 1):
					res[a][b] = res[i][j] + 1
					q.append((a, b))
		for i in range(n):
			for j in range(m):
				if res[i][j] == 10 ** 9 + 7:
					res[i][j] = -1
		return res


class cell:

	def __init__(self, x, y):
		self.x = x
		self.y = y

class Solution:

	def findDistance(self, mat, m, n):
		visit = [[False for i in range(n)] for i in range(m)]
		c = 1
		q = []
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 'B':
					q.append(cell(i, j))
					mat[i][j] = 0
					visit[i][j] = True
		while len(q):
			s = len(q)
			while s > 0:
				t = q[0]
				if t.x - 1 >= 0 and mat[t.x - 1][t.y] == 'O' and (visit[t.x - 1][t.y] == False):
					mat[t.x - 1][t.y] = c
					q.append(cell(t.x - 1, t.y))
					visit[t.x - 1][t.y] = True
				if t.x + 1 < m and mat[t.x + 1][t.y] == 'O' and (visit[t.x + 1][t.y] == False):
					mat[t.x + 1][t.y] = c
					q.append(cell(t.x + 1, t.y))
					visit[t.x + 1][t.y] = True
				if t.y - 1 >= 0 and mat[t.x][t.y - 1] == 'O' and (visit[t.x][t.y - 1] == False):
					mat[t.x][t.y - 1] = c
					q.append(cell(t.x, t.y - 1))
					visit[t.x][t.y - 1] = True
				if t.y + 1 < n and mat[t.x][t.y + 1] == 'O' and (visit[t.x][t.y + 1] == False):
					mat[t.x][t.y + 1] = c
					q.append(cell(t.x, t.y + 1))
					visit[t.x][t.y + 1] = True
				q.pop(0)
				s -= 1
			c += 1
		for i in range(m):
			for j in range(n):
				if visit[i][j] == False:
					mat[i][j] = -1
		return mat


INV = 10 ** 9
from collections import deque

class Solution:

	def findDistance(self, M, m, n):
		q = deque()
		for i in range(m):
			for j in range(n):
				if M[i][j] == 'B':
					M[i][j] = 0
					q.append((i, j, 0))
				elif M[i][j] == 'W':
					M[i][j] = -1
				else:
					M[i][j] = INV
		while q:
			(i, j, d) = q.popleft()
			for (ni, nj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				if 0 <= ni < m and 0 <= nj < n and (M[ni][nj] > d):
					M[ni][nj] = d + 1
					q.append((ni, nj, d + 1))
		for i in range(m):
			for j in range(n):
				if M[i][j] == INV:
					M[i][j] = -1
		return M


class Solution:

	def findDistance(self, matrix, m, n):

		def possible(i, j, m, n):
			return i >= 0 and j >= 0 and (i < m) and (j < n)
		visited = [[False for i in range(n)] for j in range(m)]
		cost = [[-1 for i in range(n)] for j in range(m)]

		def solver(i, j, matrix, m, n):
			q = [[i, j, 0]]
			while q:
				curr = q.pop(0)
				(i, j, dist) = (curr[0], curr[1], curr[2])
				a = [-1, 0, 1, 0]
				b = [0, -1, 0, 1]
				for k in range(4):
					(r, c) = (i + a[k], j + b[k])
					if possible(r, c, m, n):
						if visited[r][c] == False and matrix[r][c] == 'O':
							visited[r][c] = True
							cost[r][c] = dist + 1
							q.append([r, c, dist + 1])
							continue
						elif visited[r][c] == False and matrix[r][c] == 'B':
							visited[r][c] = True
							cost[r][c] = 0
							q.append([r, c, 0])
							continue
						elif visited[r][c] == True and matrix[r][c] == 'O':
							if cost[r][c] > dist + 1:
								cost[r][c] = dist + 1
								q.append([r, c, dist + 1])
								continue
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B' and visited[i][j] == False:
					cost[i][j] = 0
					solver(i, j, matrix, m, n)
		return cost


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
		queue = deque()
		result = [[-1 for col in range(n)] for row in range(m)]
		for row in range(m):
			for col in range(n):
				if matrix[row][col] == 'B':
					queue.append((row, col))
					result[row][col] = 0
		while queue:
			(row, col) = queue.popleft()
			for direction in directions:
				n_row = row + direction[0]
				n_col = col + direction[1]
				if n_row > -1 and n_row < m and (n_col > -1) and (n_col < n):
					if matrix[n_row][n_col] == 'O' and result[n_row][n_col] == -1:
						queue.append((n_row, n_col))
						result[n_row][n_col] = result[row][col] + 1
		return result


from collections import deque

class Solution:
	DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

	def findDistance(self, matrix, m, n):

		def inMatrix(i, j, m, n):
			return 0 <= i < m and 0 <= j < n
		q = deque()
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					q.append((i, j))
		d = 1
		while q:
			for _ in range(len(q)):
				(i, j) = q.popleft()
				for dir in self.DIRS:
					ii = i + dir[0]
					jj = j + dir[1]
					if inMatrix(ii, jj, m, n) and matrix[ii][jj] == 'O':
						q.append((ii, jj))
						matrix[ii][jj] = d
			d += 1
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					matrix[i][j] = 0
				if matrix[i][j] == 'O' or matrix[i][j] == 'W':
					matrix[i][j] = -1
		return matrix


class Solution:

	def findDistance(self, a, m, n):
		q = []
		for i in range(m):
			for j in range(n):
				if a[i][j] == 'B':
					q.append([i, j, 0])
				elif a[i][j] == 'W':
					a[i][j] = -1
		while q:
			p = q.pop(0)
			a[p[0]][p[1]] = p[2]
			x_pos = [-1, 0, 0, 1]
			y_pos = [0, -1, 1, 0]
			for i in range(len(x_pos)):
				nx = x_pos[i] + p[0]
				ny = y_pos[i] + p[1]
				if nx < 0 or nx >= m or ny < 0 or (ny >= n):
					continue
				if a[nx][ny] == 'O':
					q.append([nx, ny, p[2] + 1])
					a[nx][ny] = ''
		for i in range(m):
			for j in range(n):
				if a[i][j] == 'O':
					a[i][j] = -1
		return a


class Solution:

	def findDistance(self, matrix, m, n):
		_max = 100000000000.0
		Dist = [[_max for _ in range(n)] for _ in range(m)]
		Visited = [[False for _ in range(n)] for _ in range(m)]
		dx = [0, 1, -1, 0]
		dy = [1, 0, 0, -1]
		q = []
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					Dist[i][j] = 0
					q.append([i, j])
					Visited[i][j] = True
				elif matrix[i][j] == 'W':
					Dist[i][j] = -1
		while q:
			(x, y) = q.pop(0)
			for i in range(4):
				xx = x + dx[i]
				yy = y + dy[i]
				if xx >= 0 and xx < m and (yy >= 0) and (yy < n) and (Visited[xx][yy] == False) and (matrix[xx][yy] != 'W'):
					Dist[xx][yy] = Dist[x][y] + 1
					Visited[xx][yy] = True
					q.append([xx, yy])
		for i in range(m):
			for j in range(n):
				if Dist[i][j] == _max:
					Dist[i][j] = -1
		return Dist


class Solution:

	def findDistance(self, grid, m, n):
		dx = [0, -1, 0, 1]
		dy = [-1, 0, 1, 0]
		ans = [[float('inf') for j in range(n)] for i in range(m)]
		Q = []
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'B':
					ans[i][j] = 0
					Q.append((i, j))
				if grid[i][j] == 'W':
					ans[i][j] = -1
		while Q != []:
			(i, j) = Q.pop(0)
			for k in range(4):
				x = i + dx[k]
				y = j + dy[k]
				if x >= 0 and y >= 0 and (x < m) and (y < n) and (grid[x][y] == 'O') and (ans[x][y] > ans[i][j] + 1):
					ans[x][y] = ans[i][j] + 1
					Q.append((x, y))
		for i in range(m):
			for j in range(n):
				if ans[i][j] == float('inf'):
					ans[i][j] = -1
		return ans


class Solution:

	def findDistance(self, matrix, m, n):
		memo = [[-1 for _ in range(n)] for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					memo[i][j] = 0
				elif matrix[i][j] == 'O':
					if i > 0 and memo[i - 1][j] >= 0:
						memo[i][j] = memo[i - 1][j] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i - 1][j] + 1)
					if j > 0 and memo[i][j - 1] >= 0:
						memo[i][j] = memo[i][j - 1] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i][j - 1] + 1)
		for i in range(m):
			for j in range(n - 1, -1, -1):
				if matrix[i][j] == 'O':
					if i > 0 and memo[i - 1][j] >= 0:
						memo[i][j] = memo[i - 1][j] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i - 1][j] + 1)
					if j + 1 < n and memo[i][j + 1] >= 0:
						memo[i][j] = memo[i][j + 1] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i][j + 1] + 1)
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if matrix[i][j] == 'O':
					if i + 1 < m and memo[i + 1][j] >= 0:
						memo[i][j] = memo[i + 1][j] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i + 1][j] + 1)
					if j + 1 < n and memo[i][j + 1] >= 0:
						memo[i][j] = memo[i][j + 1] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i][j + 1] + 1)
		for i in range(m - 1, -1, -1):
			for j in range(n):
				if matrix[i][j] == 'O':
					if i + 1 < m and memo[i + 1][j] >= 0:
						memo[i][j] = memo[i + 1][j] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i + 1][j] + 1)
					if j > 0 and memo[i][j - 1] >= 0:
						memo[i][j] = memo[i][j - 1] + 1 if memo[i][j] < 0 else min(memo[i][j], memo[i][j - 1] + 1)
		return memo


class Solution:

	def findDistance(self, matrix, m, n):
		temp = [[0 for j in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'W':
					temp[i][j] = -1
				elif matrix[i][j] == 'B':
					temp[i][j] = 0
				else:
					temp[i][j] = 100000
		for k in range(m):
			for g in range(n):
				visited = []
				if temp[k][g] == 0:
					visited.append([k, g])
					while visited != []:
						l = visited.pop(0)
						i = l[0]
						j = l[1]
						if i + 1 < m and temp[i + 1][j] != -1:
							temp[i + 1][j] = min(temp[i][j] + 1, temp[i + 1][j])
							if temp[i + 1][j] == temp[i][j] + 1:
								visited.append([i + 1, j])
						if i - 1 >= 0 and temp[i - 1][j] != -1:
							temp[i - 1][j] = min(temp[i][j] + 1, temp[i - 1][j])
							if temp[i - 1][j] == temp[i][j] + 1:
								visited.append([i - 1, j])
						if j + 1 < n and temp[i][j + 1] != -1:
							temp[i][j + 1] = min(temp[i][j] + 1, temp[i][j + 1])
							if temp[i][j + 1] == temp[i][j] + 1:
								visited.append([i, j + 1])
						if j - 1 >= 0 and temp[i][j - 1] != -1:
							temp[i][j - 1] = min(temp[i][j] + 1, temp[i][j - 1])
							if temp[i][j - 1] == temp[i][j] + 1:
								visited.append([i, j - 1])
		for i in range(m):
			for j in range(n):
				if temp[i][j] == 100000:
					temp[i][j] = -1
		return temp


from heapq import heappop, heappush, heapify

class Solution:

	def isSafe(self, x, y, n, m):
		if x < n and y < m and (x >= 0) and (y >= 0):
			return True
		return False

	def BFS(self, q, visited, dist, matrix):
		step = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		while len(q):
			(res, i, j) = heappop(q)
			for k in range(4):
				x = i + step[k][0]
				y = j + step[k][1]
				if self.isSafe(x, y, len(matrix), len(matrix[0])) and (not visited[x][y]) and (matrix[x][y] != 'W'):
					dist[x][y] = res + 1
					visited[x][y] = True
					heappush(q, (dist[x][y], x, y))

	def findDistance(self, matrix, m, n):
		(n, m) = (m, n)
		dist = [[-1 for _ in range(m)] for _ in range(n)]
		visited = [[False for _ in range(m)] for _ in range(n)]
		q = []
		heapify(q)
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 'B':
					heappush(q, (0, i, j))
					dist[i][j] = 0
					visited[i][j] = True
		self.BFS(q, visited, dist, matrix)
		return dist


class Solution:

	def findDistance(self, matrix, m, n):
		res = []
		for _ in range(m):
			lst = []
			for j in range(n):
				lst.append(float('inf'))
			res.append(lst)
		q = []
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					res[i][j] = 0
					q.append([i, j])
				if matrix[i][j] == 'W':
					res[i][j] = -1
		change_i = [0, 1, 0, -1]
		change_j = [1, 0, -1, 0]
		while q:
			curr = q.pop(0)
			i = curr[0]
			j = curr[1]
			for k in range(len(change_i)):
				if 0 <= i + change_i[k] < m and 0 <= j + change_j[k] < n and (res[i + change_i[k]][j + change_j[k]] == float('inf')):
					res[i + change_i[k]][j + change_j[k]] = res[i][j] + 1
					q.append([i + change_i[k], j + change_j[k]])
		for i in range(m):
			for j in range(n):
				if res[i][j] == float('inf'):
					res[i][j] = -1
		return res


from collections import deque
INT_MAX = 10 ** 9 + 1

class Solution:

	def findDistance(self, matrix, m, n):
		INT_MAX = 10 ** 9 + 1
		q = deque([])
		ans = [[INT_MAX for j in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					ans[i][j] = 0
					q.append((i, j))
				elif matrix[i][j] == 'W':
					ans[i][j] = -1
		bfs(matrix, q, ans, m, n)
		return ans

def bfs(matrix, q, ans, m, n):
	while q:
		(a, b) = q.popleft()
		for (i, j) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
			if a + i >= 0 and a + i < m and (b + j >= 0) and (b + j < n) and (matrix[a + i][b + j] == 'O') and (ans[a + i][b + j] > ans[a][b] + 1):
				ans[a + i][b + j] = ans[a][b] + 1
				q.append((a + i, b + j))
	for i in range(m):
		for j in range(n):
			if ans[i][j] == INT_MAX:
				ans[i][j] = -1
	return ans


from collections import defaultdict

class Solution:

	def __init__(self):
		self.op = []

	def helper(self, matrix, m, n, i, j, prev):
		if ((i < 0 or i >= m) or (j >= n or j < 0)) or (matrix[i][j] == 'W' or matrix[i][j] == 'B') or self.op[i][j] > 0:
			return []
		t = prev + 1
		if self.op[i][j] != -1:
			if t < self.op[i][j]:
				self.op[i][j] = t
		else:
			self.op[i][j] = t
		return [i, j]

	def findDistance(self, matrix, m, n):
		dic = defaultdict(list)
		lis = []
		self.op = []
		for i in range(0, m):
			t = []
			for j in range(0, n):
				t.append(-1)
			self.op.append(t)
		for i in range(0, m):
			for j in range(0, n):
				if matrix[i][j] == 'B':
					self.op[i][j] = 0
					lis.append([i, j])
		while lis:
			t = lis[0]
			i = t[0]
			j = t[1]
			o = self.helper(matrix, m, n, i - 1, j, self.op[i][j])
			if len(o) > 0:
				lis.append(o)
			o = self.helper(matrix, m, n, i, j - 1, self.op[i][j])
			if len(o) > 0:
				lis.append(o)
			o = self.helper(matrix, m, n, i + 1, j, self.op[i][j])
			if len(o) > 0:
				lis.append(o)
			o = self.helper(matrix, m, n, i, j + 1, self.op[i][j])
			if len(o) > 0:
				lis.append(o)
			del lis[0]
		return self.op


class Solution:

	def solve(self, mat, res, cost, i, j, m, n):
		if self.isValid(mat, i, j, m, n) or cost == 0:
			if res[i][j] == 0 or res[i][j] > cost:
				res[i][j] = cost
				self.solve(mat, res, cost + 1, i, j - 1, m, n)
				self.solve(mat, res, cost + 1, i, j + 1, m, n)
				self.solve(mat, res, cost + 1, i - 1, j, m, n)
				self.solve(mat, res, cost + 1, i + 1, j, m, n)

	def isValid(self, mat, i, j, m, n):
		return i >= 0 and j >= 0 and (i < m) and (j < n) and (mat[i][j] == 'O')

	def findDistance(self, mat, m, n):
		res = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 'B':
					self.solve(mat, res, 0, i, j, m, n)
		for i in range(m):
			for j in range(n):
				if res[i][j] == 0:
					res[i][j] = -1
				if mat[i][j] == 'B':
					res[i][j] = 0
				if mat[i][j] == 'W':
					res[i][j] = -1
		return res


from collections import deque
dr = [-1, 0, 0, 1]
dc = [0, -1, 1, 0]

class Solution:

	def findDistance(self, matrix, m, n):
		ret = [[-1 for _ in range(n)] for _ in range(m)]
		q = deque()
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					ret[i][j] = 0
					q.append((i, j))
		while len(q):
			r = q[0][0]
			c = q[0][1]
			q.popleft()
			for i in range(4):
				nextr = r + dr[i]
				nextc = c + dc[i]
				if nextr >= 0 and nextr < m and (nextc >= 0) and (nextc < n):
					if ret[nextr][nextc] == -1 and matrix[nextr][nextc] == 'O':
						ret[nextr][nextc] = ret[r][c] + 1
						q.append((nextr, nextc))
		return ret


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		que = deque()
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					que.append((i, j, 0))
					matrix[i][j] = 0
				elif matrix[i][j] == 'W':
					matrix[i][j] = -1
		xi = [1, -1, 0, 0]
		yi = [0, 0, 1, -1]
		vis = set()
		while que:
			(i, j, l) = que.popleft()
			for d in range(4):
				x = i + xi[d]
				y = j + yi[d]
				if x < 0 or x >= m or y < 0 or (y >= n):
					continue
				if (x, y) in vis:
					continue
				if matrix[x][y] == -1 or matrix[x][y] == 0:
					continue
				if matrix[x][y] == 'O':
					matrix[x][y] = l + 1
				else:
					matrix[x][y] = min(matrix[x][y], l + 1)
				que.append((x, y, l + 1))
				vis.add((x, y))
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		(m, n) = (len(matrix), len(matrix[0]))

		def bfs(y, x):
			visited = {(y, x)}
			q = deque([(y, x, 0)])
			while q:
				(y0, x0, d) = q.popleft()
				if d > 0 and (matrix[y0][x0] == 'O' or matrix[y0][x0] > d):
					matrix[y0][x0] = d
				for (y, x) in [(y0 + 1, x0), (y0 - 1, x0), (y0, x0 + 1), (y0, x0 - 1)]:
					if y < 0 or y >= m or x < 0 or (x >= n) or ((y, x) in visited):
						continue
					if matrix[y][x] == 'W' or matrix[y][x] == 'B':
						continue
					q.append((y, x, d + 1))
					visited.add((y, x))
		for y in range(m):
			for x in range(n):
				if matrix[y][x] == 'B':
					bfs(y, x)
		for y in range(m):
			for x in range(n):
				if matrix[y][x] == 'B':
					matrix[y][x] = 0
				if matrix[y][x] == 'W' or matrix[y][x] == 'O':
					matrix[y][x] = -1
		return matrix


class Solution:

	def findDistance(self, matrix, m, n):
		m = len(matrix)
		n = len(matrix[0])

		def issafe(ith, jth):
			if ith >= 0 and ith < len(matrix) and (jth >= 0) and (jth < len(matrix[0])) and (visited[ith][jth] == False) and (matrix[ith][jth] == 'O'):
				return True
			return False
		q = []
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'W':
					matrix[i][j] = -1
				elif matrix[i][j] == 'B':
					q.append([i, j])
		neighbours = [[0, 1], [1, 0], [-1, 0], [0, -1]]
		level = -1
		while q:
			size = len(q)
			level += 1
			while size > 0:
				rem = q.pop(0)
				if matrix[rem[0]][rem[1]] == 'O':
					matrix[rem[0]][rem[1]] = level
				visited[rem[0]][rem[1]] = True
				if matrix[rem[0]][rem[1]] == 'B':
					matrix[rem[0]][rem[1]] = 0
				for neighbour in neighbours:
					if issafe(rem[0] + neighbour[0], rem[1] + neighbour[1]):
						q.append([rem[0] + neighbour[0], rem[1] + neighbour[1]])
				size -= 1
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


class Solution:

	def dfs(self, i, j, matrix, visited):
		if 0 <= i < len(matrix) and 0 <= j < len(matrix[0]) and (visited[i][j] != 1) and (matrix[i][j] != 'W'):
			if matrix[i][j] == 'B':
				return 0
			visited[i][j] = 1
			l = 1 + self.dfs(i + 1, j, matrix, visited)
			r = 1 + self.dfs(i - 1, j, matrix, visited)
			k = 1 + self.dfs(i, j + 1, matrix, visited)
			p = 1 + self.dfs(i, j - 1, matrix, visited)
			visited[i][j] = 0
			return min(l, min(r, min(k, p)))
		return float('inf')

	def findDistance(self, matrix, m, n):
		out = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
		visited = [[0 for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'O':
					out[i][j] = -1
				elif matrix[i][j] == 'B':
					out[i][j] = 0
				elif matrix[i][j] == 'W':
					out[i][j] = -1
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'O':
					ou = self.dfs(i, j, matrix, visited)
					if ou < float('inf'):
						out[i][j] = ou
		return out


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		ans = [[1000000] * n for _ in range(m)]
		que = deque([])
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					ans[i][j] = 0
					que.append((i, j))
				elif matrix[i][j] == 'W':
					ans[i][j] = -1
		drr = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		while que:
			(i, j) = que.popleft()
			for k in range(4):
				(x, y) = (i + drr[k][0], j + drr[k][1])
				if x >= 0 and x < m and (y >= 0) and (y < n) and (matrix[x][y] == 'O') and (ans[x][y] > ans[i][j] + 1):
					ans[x][y] = ans[i][j] + 1
					que.append((x, y))
		for i in range(m):
			for j in range(n):
				if ans[i][j] == 1000000:
					ans[i][j] = -1
		return ans


class Solution:

	def findDistance(self, mat, m, n):
		n = len(matrix)
		m = len(matrix[0])
		ans = [[9999999] * m for i in range(n)]
		rx = [1, 0, -1, 0]
		cx = [0, 1, 0, -1]

		def BFS(mat, n, m, ans, i, j):
			visit = set()
			q = [[i, j, 0]]
			while q:
				val = q.pop(0)
				visit.add((val[0], val[1]))
				for k in range(4):
					rr = val[0] + rx[k]
					cc = val[1] + cx[k]
					if rr >= 0 and cc >= 0 and (rr < n) and (cc < m) and ((rr, cc) not in visit) and (mat[rr][cc] == 'O'):
						ans[rr][cc] = min(ans[rr][cc], val[2] + 1)
						q.append((rr, cc, val[2] + 1))
						visit.add((rr, cc))
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'B':
					BFS(mat, n, m, ans, i, j)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'W':
					ans[i][j] = -1
				if mat[i][j] == 'B':
					ans[i][j] = 0
				if mat[i][j] == 'O' and ans[i][j] == 9999999:
					ans[i][j] = -1
		return ans


from collections import deque
dr = [-1, 0, 0, 1]
dc = [0, -1, 1, 0]

class Solution:

	def findDistance(self, matrix, m, n):
		q = deque()
		mat = [[-1 for i in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					mat[i][j] = 0
					q.append((i, j))
		while len(q):
			r = q[0][0]
			c = q[0][1]
			q.popleft()
			for i in range(4):
				rnext = dr[i] + r
				cnext = dc[i] + c
				if rnext >= 0 and rnext < m and (cnext >= 0) and (cnext < n):
					if mat[rnext][cnext] == -1 and matrix[rnext][cnext] == 'O':
						mat[rnext][cnext] = mat[r][c] + 1
						q.append((rnext, cnext))
		return mat


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):

		def issafe(i, j):
			if i >= 0 and i < len(matrix) and (j >= 0) and (j < len(matrix[0])) and (v[i][j] == False) and (matrix[i][j] == 'O'):
				return True
			return False
		q = deque()
		v = [[False for i in range(len(matrix[0]))] for j in range(len(matrix))]
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'W':
					matrix[i][j] = -1
				elif matrix[i][j] == 'B':
					q.append([i, j])
		mov = [[0, 1], [1, 0], [-1, 0], [0, -1]]
		l = -1
		while q:
			s = len(q)
			l += 1
			while s:
				el = q.popleft()
				if matrix[el[0]][el[1]] == 'O':
					matrix[el[0]][el[1]] = l
				v[el[0]][el[1]] = True
				if matrix[el[0]][el[1]] == 'B':
					matrix[el[0]][el[1]] = 0
				for x in mov:
					if issafe(el[0] + x[0], el[1] + x[1]):
						q.append([el[0] + x[0], el[1] + x[1]])
				s -= 1
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'O':
					matrix[i][j] = -1
		return matrix


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		vis = set([])
		q = deque([])
		for row in range(len(matrix)):
			for col in range(len(matrix[0])):
				if matrix[row][col] == 'B':
					vis.add((row, col))
					matrix[row][col] = 0
					q.append((row, col, 0))
				elif matrix[row][col] == 'W':
					vis.add((row, col))
					matrix[row][col] = -1
				else:
					matrix[row][col] = -1
		di = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		while q:
			(i, j, cost) = q.popleft()
			if (i, j) not in vis:
				matrix[i][j] = cost
				vis.add((i, j))
			for (a, b) in di:
				(na, nb) = (i + a, j + b)
				if (na, nb) not in vis and na >= 0 and (nb >= 0) and (na < m) and (nb < n):
					q.append((na, nb, cost + 1))
		return matrix


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		queue = deque()
		zeros = {}
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'W':
					matrix[i][j] = -1
				elif matrix[i][j] == 'B':
					matrix[i][j] = 0
					queue.append([i, j, 0])
				else:
					zeros[i, j] = -1
		while queue:
			t = len(queue)
			for _ in range(t):
				cur = queue.popleft()
				for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
					new_x = cur[0] + d[0]
					new_y = cur[1] + d[1]
					if 0 <= new_x < m and 0 <= new_y < n and (matrix[new_x][new_y] == 'O'):
						l = cur[2] + 1
						matrix[new_x][new_y] = l
						queue.append([new_x, new_y, l])
						del zeros[new_x, new_y]
		for each in zeros:
			matrix[each[0]][each[1]] = -1
		return matrix


class Solution:

	def findDistance(self, matrix, m, n):
		a = [[-1 for i in range(n)] for i in range(m)]
		queue = []

		def visit(i, j, m, o):
			if i < 0 or j < 0 or i > len(m) - 1 or (j > len(m[0]) - 1):
				return False
			if o[i][j] != -1:
				return False
			if m[i][j] != 'O':
				return False
			return True
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					queue.append([i, j, 0])
					a[i][j] = 0
		row = [1, 0, -1, 0]
		col = [0, 1, 0, -1]
		while len(queue) > 0:
			curr = queue.pop(0)
			for i in range(4):
				if visit(curr[0] + row[i], curr[1] + col[i], matrix, a):
					a[curr[0] + row[i]][curr[1] + col[i]] = curr[2] + 1
					queue.append([curr[0] + row[i], curr[1] + col[i], curr[2] + 1])
		return a


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		q = deque()
		for i in range(0, len(matrix)):
			for j in range(0, len(matrix[0])):
				if matrix[i][j] == 'B':
					matrix[i][j] = 0
					q.append((i, j, 0))
		while q:
			temp = q.popleft()
			r = temp[0]
			c = temp[1]
			dist = temp[2]
			for i in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
				if i[0] >= 0 and i[0] < len(matrix) and (i[1] >= 0) and (i[1] < len(matrix[0])) and (matrix[i[0]][i[1]] == 'O'):
					matrix[i[0]][i[1]] = dist + 1
					q.append((i[0], i[1], dist + 1))
		for i in range(0, len(matrix)):
			for j in range(0, len(matrix[0])):
				if matrix[i][j] == 'W' or matrix[i][j] == 'O':
					matrix[i][j] = '-1'
		return matrix


import collections

class Solution:

	def findDistance(self, matrix, rows, cols):
		ans = [[float('inf')] * cols for _ in range(rows)]
		queue = collections.deque()
		for i in range(rows):
			for j in range(cols):
				if matrix[i][j] == 'B':
					ans[i][j] = 0
					queue.append((i, j))
				elif matrix[i][j] == 'W':
					ans[i][j] = -1
		dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		while queue:
			(x, y) = queue.popleft()
			for (i, j) in dirs:
				nx = i + x
				ny = j + y
				if 0 <= nx < rows and 0 <= ny < cols and (matrix[nx][ny] == 'O') and (ans[nx][ny] > ans[x][y] + 1):
					ans[nx][ny] = ans[x][y] + 1
					queue.append((nx, ny))
		for i in range(rows):
			for j in range(cols):
				if ans[i][j] == float('inf'):
					ans[i][j] = -1
		return ans


class Solution:

	def findDistance(self, matrix, m, n):
		queue = []
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					matrix[i][j] = 0
					queue.append([i, j, 0])
				if matrix[i][j] == 'W':
					matrix[i][j] = -1
				if matrix[i][j] == 'O':
					matrix[i][j] = float('inf') - 1
		while queue:
			(first, second, cost) = queue.pop(0)
			for (i, j) in [[-1, 0], [0, 1], [1, 0], [0, -1]]:
				if first + i >= 0 and first + i < m and (second + j >= 0) and (second + j < n):
					if matrix[first + i][second + j] == 0:
						matrix[first + i][second + j] = 0
					elif matrix[first + i][second + j] == -1:
						matrix[first + i][second + j] = -1
					elif matrix[first + i][second + j] > cost + 1:
						matrix[first + i][second + j] = cost + 1
						queue.append([first + i, second + j, cost + 1])
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == float('inf'):
					matrix[i][j] = -1
		return matrix


arl = [-1, 0, 1, 0]
arr = [0, -1, 0, 1]

class Solution:

	def findDistance(self, matrix, m, n):
		res = [[-1] * n for _ in range(m)]
		queue = []
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					res[i][j] = 0
					queue.append((i, j))
		while len(queue) > 0:
			x = queue.pop(0)
			r = x[0]
			l = x[1]
			for i in range(4):
				newr = r + arl[i]
				newc = l + arr[i]
				if 0 <= newr and 0 <= newc and (newr < m) and (newc < n):
					if matrix[newr][newc] == 'O' and res[newr][newc] == -1:
						res[newr][newc] = res[r][l] + 1
						queue.append((newr, newc))
		return res
		return [[]]


class Solution:

	def findDistance(self, l, m, n):
		(n, m) = (len(l), len(l[0]))
		dp = [[float('inf') for i in range(m)] for j in range(n)]
		t = [(0, 1), (1, 0), (0, -1), (-1, 0)]

		def check(i, j):
			if i >= 0 and j >= 0 and (i < n) and (j < m) and (l[i][j] == 'O'):
				return True
			return False

		def fun(dp, i, j):
			for k in t:
				x = i + k[0]
				y = j + k[1]
				if check(x, y):
					if dp[x][y] >= dp[i][j] + 1:
						dp[x][y] = dp[i][j] + 1
						fun(dp, x, y)
		for i in range(n):
			for j in range(m):
				if l[i][j] == 'B':
					dp[i][j] = 0
					fun(dp, i, j)
				elif l[i][j] == 'W':
					dp[i][j] = -1
		for i in range(n):
			for j in range(m):
				if l[i][j] == 'O' and dp[i][j] == float('inf'):
					dp[i][j] = -1
		return dp


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		queue = deque()
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					queue.append((i, j))
		depth = 0
		while len(queue) > 0:
			size = len(queue)
			for i in range(size):
				indices = queue.popleft()
				x = indices[0]
				y = indices[1]
				if isinstance(matrix[x][y], int):
					continue
				if matrix[x][y] == 'W':
					matrix[x][y] = -1
					continue
				matrix[x][y] = depth
				if x > 0:
					queue.append((x - 1, y))
				if x < m - 1:
					queue.append((x + 1, y))
				if y > 0:
					queue.append((x, y - 1))
				if y < n - 1:
					queue.append((x, y + 1))
			depth += 1
		for i in range(m):
			for j in range(n):
				if isinstance(matrix[i][j], str):
					matrix[i][j] = -1
		return matrix


from collections import deque

class Solution:

	def findDistance(self, grid, m, n):

		def solve(r, c):
			q = deque([(0, r, c)])
			vis = set()
			di = [[0, 1], [1, 0], [-1, 0], [0, -1]]
			vis.add((r, c))
			while q:
				(d, x, y) = q.popleft()
				if grid[x][y] == 'B':
					return d
				for (i, j) in di:
					(nx, ny) = (x + i, y + j)
					if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and ((nx, ny) not in vis) and (grid[nx][ny] != 'W'):
						q.append((d + 1, nx, ny))
						vis.add((nx, ny))
			return -1
		ans = [[0] * len(grid[0]) for _ in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'O':
					ans[i][j] = solve(i, j)
				elif grid[i][j] == 'W':
					ans[i][j] = -1
		return ans


from itertools import *
from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):

		def isValid(x, y):
			return 0 <= x < m and 0 <= y < n
		res = [[-1 for _ in range(n)] for _ in range(m)]
		q = deque([])
		vis = set([])
		for (x, y) in product(range(m), range(n)):
			if matrix[x][y] == 'B':
				q.append((x, y, 0))
				vis.add((x, y))
		while q:
			(x, y, c) = q.popleft()
			res[x][y] = c
			for (nx, ny) in [(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]:
				if isValid(nx, ny) and matrix[nx][ny] == 'O' and ((nx, ny) not in vis):
					q.append((nx, ny, c + 1))
					vis.add((nx, ny))
		return res


from collections import deque

class Solution:

	def findDistance(self, mt, row, col):
		res = [[-2 for c in range(col)] for r in range(row)]
		q = deque()
		for r in range(row):
			for c in range(col):
				if mt[r][c] == 'B':
					q.append([r, c])
					res[r][c] = 0
				elif mt[r][c] == 'W':
					res[r][c] = -1
		dx = [-1, 1, 0, 0]
		dy = [0, 0, 1, -1]
		while len(q):
			(x, y) = q.popleft()
			for i in range(4):
				(nx, ny) = (x + dx[i], y + dy[i])
				if nx < 0 or ny < 0 or nx >= row or (ny >= col) or (mt[nx][ny] != 'O') or (res[nx][ny] > 0):
					continue
				res[nx][ny] = res[x][y] + 1
				q.append([nx, ny])
		for r in range(row):
			for c in range(col):
				if res[r][c] == -2:
					res[r][c] = -1
		return res


class Solution:

	def findDistance(self, matrix, m, n):
		listOfBombs = []
		ans = [[0 for j in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					listOfBombs.append((i, j))
					ans[i][j] = 0
				if matrix[i][j] == 'W':
					ans[i][j] = -1
				if matrix[i][j] == 'O':
					ans[i][j] = 10000007
		for ele in listOfBombs:
			visited = [[False for j in range(n)] for i in range(m)]
			q = []
			q.append(ele)
			while len(q) != 0:
				x = q[0][0]
				y = q[0][1]
				q.pop(0)
				if x + 1 < m and matrix[x + 1][y] == 'O' and (not visited[x + 1][y]):
					ans[x + 1][y] = min(ans[x + 1][y], ans[x][y] + 1)
					visited[x + 1][y] = True
					q.append((x + 1, y))
				if x - 1 >= 0 and matrix[x - 1][y] == 'O' and (not visited[x - 1][y]):
					ans[x - 1][y] = min(ans[x - 1][y], ans[x][y] + 1)
					visited[x - 1][y] = True
					q.append((x - 1, y))
				if y + 1 < n and matrix[x][y + 1] == 'O' and (not visited[x][y + 1]):
					ans[x][y + 1] = min(ans[x][y + 1], ans[x][y] + 1)
					visited[x][y + 1] = True
					q.append((x, y + 1))
				if y - 1 >= 0 and matrix[x][y - 1] == 'O' and (not visited[x][y - 1]):
					ans[x][y - 1] = min(ans[x][y - 1], ans[x][y] + 1)
					visited[x][y - 1] = True
					q.append((x, y - 1))
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'O' and ans[i][j] == 10000007:
					ans[i][j] = -1
		return ans


from collections import deque

class Solution:

	def findDistance(self, matrix, m, n):
		queue = deque()
		ans = [[float('inf') for _ in range(n)] for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'B':
					queue.append((i, j, 0))
					ans[i][j] = 0
				elif matrix[i][j] == 'W':
					ans[i][j] = -1
		while queue:
			(i, j, d) = queue.popleft()
			for (x, y) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
				(p, q) = (i + x, j + y)
				if 0 <= p < m and 0 <= q < n and (ans[p][q] > d + 1):
					ans[p][q] = d + 1
					queue.append((p, q, d + 1))
		for i in range(m):
			for j in range(n):
				if ans[i][j] == float('inf'):
					ans[i][j] = -1
		return ans