Geek's village is represented by a 2-D matrix of characters of size n*m, where
H - Represents a house
W - Represents a well
. - Represents an open ground
N - Prohibited area(Not allowed to enter this area)
Every house in the village needs to take water from a well, as the family members are so busy with their work, so every family wants to take the water from a well in minimum time, which is possible only if they have to cover as less distance as possible. Your task is to determine the minimum distance that a person in the house should travel to take out the water and carry it back to the house.
A person is allowed to move only in four directions left, right, up, and down. That means if he/she is the cell (i,j), then the possible cells he/she can reach in one move are (i,j-1),(i,j+1),(i-1,j),(i+1,j), and the person is not allowed to move out of the grid.
Note: For all the cells containing 'N', 'W' and '.' our answer should be 0, and for all the houses where there is no possibility of taking water our answer should be -1.
Example 1:
Input:
n = 3
m = 3
c[][]: H H H
       H W H
       H H H
Output:
4 2 4 
2 0 2 
4 2 4
Explanation:
There is only one well hence all the houses present
in the corner of matrix will have to travel a minimum
distance of 4, 2 is for house to well and other two is
for well to house. And rest of the houses have to travel
a minimum distance of 2 (House -> Well -> House).
Example 2:
Input:
n = 5
m = 5
c[][]: H N H H H
       N N H H W
       W H H H H
       H H H H H
       H H H H H
Output:
-1 0 6 4 2 
0 0 4 2 0 
0 2 4 4 2 
2 4 6 6 4 
4 6 8 8 6
Explanation:
There is no way any person from the house in
cell (0,0) can take the water from any well, and
for rest of the houses there is same type of
strategy we have to follow as followed in example 1. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function geekAndWells() which takes n and m, dimensions of the grid, and a 2-D grid of size n*m and returns a 2-D array containing the minimum distance for all the houses as explained above.
Expected Time Complexity: O(n*m)
Expected Space Complexity: O(n*m)
Constraints:
1 <= n <= 10^3
1 <= m <= 10^3

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal

Starter code: #User function Template for python3





from typing import List



class Solution:

    def chefAndWells(self, n : int, m : int, c : List[List[str]]) -> List[List[int]]:

        

        pass



Solutions:
from typing import List, Tuple
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		dist = [[-1 for _ in range(m)] for _ in range(n)]
		vis = [[False for _ in range(m)] for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					q.append((i, j))
					vis[i][j] = True
				if c[i][j] == 'W' or c[i][j] == '.' or c[i][j] == 'N':
					dist[i][j] = 0
		dis = 2
		while q:
			qsize = len(q)
			for _ in range(qsize):
				(i, j) = q.popleft()
				for k in range(4):
					(curri, currj) = (i + dx[k], j + dy[k])
					if 0 <= curri < n and 0 <= currj < m and (not vis[curri][currj]) and (c[curri][currj] != 'N'):
						vis[curri][currj] = True
						q.append((curri, currj))
						if c[curri][currj] == 'H':
							dist[curri][currj] = dis
			dis += 2
		return dist


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		visited = [[False] * m for i in range(n)]
		dist = [[-1] * m for i in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					q.append([i, j])
					visited[i][j] = True
				if c[i][j] == 'W' or c[i][j] == '.' or c[i][j] == 'N':
					dist[i][j] = 0
		dis = 2
		while q:
			size = len(q)
			for p in range(size):
				x = q.popleft()
				i = x[0]
				j = x[1]
				for k in range(4):
					curri = i + dx[k]
					currj = j + dy[k]
					if curri >= 0 and currj >= 0 and (curri < n) and (currj < m) and (visited[curri][currj] == False) and (c[curri][currj] != 'N'):
						visited[curri][currj] = True
						q.append([curri, currj])
						if c[curri][currj] == 'H':
							dist[curri][currj] = dis
			dis += 2
		return dist


from typing import List
from collections import deque
kMax = 1000

class Solution:

	def chefAndWells(self, n: int, m: int, grid: List[List[str]]) -> List[List[int]]:
		diffmap = [[kMax * kMax * 4] * m for r in range(n)]
		wells = []
		homes = []
		for r in range(n):
			for c in range(m):
				if grid[r][c] == 'W':
					wells.append((r, c))
					diffmap[r][c] = 0
				elif grid[r][c] == 'H':
					homes.append((r, c))
		if wells and homes:
			self.diffuse(n, m, wells, homes, grid, diffmap)
		for r in range(n):
			for c in range(m):
				if grid[r][c] == 'H':
					if diffmap[r][c] == kMax * kMax * 4:
						diffmap[r][c] = -1
				else:
					diffmap[r][c] = 0
		return diffmap

	def diffuse(self, n, m, wells, homes, grid: List[List[str]], diffmap: List[List[int]]):
		srcq = deque([(0,) + well for well in wells])
		homes_to_be_updated = len(homes)
		while len(srcq) > 0 and homes_to_be_updated > 0:
			(mydist, r, c) = srcq.popleft()
			if diffmap[r][c] < mydist:
				continue
			for nr in [r - 1, r + 1]:
				if nr < 0 or n <= nr:
					continue
				if grid[nr][c] == 'N':
					continue
				if diffmap[nr][c] > mydist + 2:
					diffmap[nr][c] = mydist + 2
					srcq.append((diffmap[nr][c], nr, c))
					if grid[nr][c] == 'H':
						homes_to_be_updated -= 1
			for nc in [c - 1, c + 1]:
				if nc < 0 or m <= nc:
					continue
				if grid[r][nc] == 'N':
					continue
				if diffmap[r][nc] > mydist + 2:
					diffmap[r][nc] = mydist + 2
					srcq.append((diffmap[r][nc], r, nc))
					if grid[r][nc] == 'H':
						homes_to_be_updated -= 1


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		res = [[10 ** 9] * m for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					q.append((i, j))
					res[i][j] = 0
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		while q:
			(curx, cury) = q.popleft()
			for i in range(4):
				(x, y) = (curx + dx[i], cury + dy[i])
				if x >= 0 and x < n and (y < m) and (y >= 0) and (c[x][y] != 'N') and (res[x][y] > res[curx][cury] + 1):
					q.append((x, y))
					res[x][y] = res[curx][cury] + 1
		for i in range(n):
			for j in range(m):
				if c[i][j] == '.':
					res[i][j] = 0
				elif res[i][j] == 10 ** 9 and c[i][j] != 'N':
					res[i][j] = -1
				elif res[i][j] == 10 ** 9 and c[i][j] != 'H':
					res[i][j] = 0
				else:
					res[i][j] *= 2
		return res


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		ans = [[0] * m for _ in range(n)]
		visited = [[0] * m for _ in range(n)]
		queue = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					queue.append((i, j, 0))
					visited[i][j] = 1
				if c[i][j] == 'H':
					ans[i][j] = -1
		while queue:
			(i, j, dis) = queue.popleft()
			if i - 1 >= 0 and visited[i - 1][j] == 0:
				visited[i - 1][j] = 1
				value = c[i - 1][j]
				if value == 'H':
					ans[i - 1][j] = dis + 2
					queue.append((i - 1, j, dis + 2))
				elif value == '.':
					queue.append((i - 1, j, dis + 2))
			if i + 1 < n and visited[i + 1][j] == 0:
				visited[i + 1][j] = 1
				value = c[i + 1][j]
				if value == 'H':
					ans[i + 1][j] = dis + 2
					queue.append((i + 1, j, dis + 2))
				elif value == '.':
					queue.append((i + 1, j, dis + 2))
			if j - 1 >= 0 and visited[i][j - 1] == 0:
				visited[i][j - 1] = 1
				value = c[i][j - 1]
				if value == 'H':
					ans[i][j - 1] = dis + 2
					queue.append((i, j - 1, dis + 2))
				elif value == '.':
					queue.append((i, j - 1, dis + 2))
			if j + 1 < m and visited[i][j + 1] == 0:
				visited[i][j + 1] = 1
				value = c[i][j + 1]
				if value == 'H':
					ans[i][j + 1] = dis + 2
					queue.append((i, j + 1, dis + 2))
				elif value == '.':
					queue.append((i, j + 1, dis + 2))
		return ans


from typing import List, Tuple
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		not_visited = deque()
		steps = []
		dot_positions = []
		for i in range(n):
			steps.append([])
			for j in range(m):
				if c[i][j] == 'W':
					not_visited.appendleft((i, j))
					steps[i].append(0)
				elif c[i][j] == 'N':
					steps[i].append(0)
				elif c[i][j] == '.':
					dot_positions.append((i, j))
					steps[i].append(-1)
				else:
					steps[i].append(-1)
		while not_visited:
			(x, y) = not_visited.pop()
			if x + 1 < n and c[x + 1][y] not in ('W', 'N') and (steps[x + 1][y] < 0 or steps[x][y] + 2 < steps[x + 1][y]):
				not_visited.appendleft((x + 1, y))
				steps[x + 1][y] = steps[x][y] + 2
			if y + 1 < m and c[x][y + 1] not in ('W', 'N') and (steps[x][y + 1] < 0 or steps[x][y] + 2 < steps[x][y + 1]):
				not_visited.appendleft((x, y + 1))
				steps[x][y + 1] = steps[x][y] + 2
			if x - 1 >= 0 and c[x - 1][y] not in ('W', 'N') and (steps[x - 1][y] < 0 or steps[x][y] + 2 < steps[x - 1][y]):
				not_visited.appendleft((x - 1, y))
				steps[x - 1][y] = steps[x][y] + 2
			if y - 1 >= 0 and c[x][y - 1] not in ('W', 'N') and (steps[x][y - 1] < 0 or steps[x][y] + 2 < steps[x][y - 1]):
				not_visited.appendleft((x, y - 1))
				steps[x][y - 1] = steps[x][y] + 2
		for (x, y) in dot_positions:
			steps[x][y] = 0
		return steps


from collections import deque
from typing import List

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		moves = lambda i, j: [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]
		check = lambda i, j: 0 <= i < n and 0 <= j < m
		visited = [[False] * m for i in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == '.':
					continue
				if c[i][j] == 'W':
					q.append((i, j, 0))
				if c[i][j] != 'H' and c[i][j] != '.':
					visited[i][j] = True
		inf = 10000000.0
		res = [[0] * m for i in range(n)]
		while q:
			(x, y, dist) = q.popleft()
			if c[x][y] == 'H':
				res[x][y] = dist * 2
			for (i, j) in moves(x, y):
				if check(i, j) and (not visited[i][j]):
					q.append((i, j, dist + 1))
					visited[i][j] = True
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'H' and (not visited[i][j]):
					res[i][j] = -1
		return res


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		visit = [[10 ** 10] * m for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					q.append([(i, j), 0])
					visit[i][j] = 0
		lis1 = [1, -1, 0, 0]
		lis2 = [0, 0, -1, 1]
		while q:
			t = q.popleft()
			(r, c1) = t[0]
			tim = t[1]
			for i in range(4):
				nr = r + lis1[i]
				nc = c1 + lis2[i]
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (c[nr][nc] == 'H' or c[nr][nc] == '.'):
					if visit[nr][nc] > tim + 2:
						visit[nr][nc] = tim + 2
						q.append([(nr, nc), tim + 2])
		for i in range(n):
			for j in range(m):
				if c[i][j] == '.' or c[i][j] == 'N':
					visit[i][j] = 0
				if visit[i][j] == 10 ** 10:
					visit[i][j] = -1
		return visit
		pass


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, b: int, a: int, c: List[List[str]]) -> List[List[int]]:
		vis = [[10 ** 10] * a for _ in range(b)]
		q = deque()
		for i in range(b):
			for j in range(a):
				if c[i][j] == 'W':
					q.append([(i, j), 0])
					vis[i][j] = 0
		l1 = [1, -1, 0, 0]
		l2 = [0, 0, -1, 1]
		while q:
			t = q.popleft()
			(r, c1) = t[0]
			time = t[1]
			for i in range(4):
				nrow = r + l1[i]
				ncolumn = c1 + l2[i]
				if nrow >= 0 and nrow < b and (ncolumn >= 0) and (ncolumn < a) and (c[nrow][ncolumn] == 'H' or c[nrow][ncolumn] == '.'):
					if vis[nrow][ncolumn] > time + 2:
						vis[nrow][ncolumn] = time + 2
						q.append([(nrow, ncolumn), time + 2])
		for i in range(b):
			for j in range(a):
				if c[i][j] == '.' or c[i][j] == 'N':
					vis[i][j] = 0
				if vis[i][j] == 10 ** 10:
					vis[i][j] = -1
		return vis


from collections import deque
from typing import List

class Solution:

	def chefAndWells(self, n: int, m: int, l: List[List[str]]) -> List[List[int]]:
		res = []
		dx = [1, -1, 0, 0]
		dy = [0, 0, -1, 1]
		for i in range(n):
			res.append([-1] * m)
		vis = []
		for i in range(n):
			vis.append([False] * m)
			new = deque()
		for i in range(n):
			for j in range(m):
				if l[i][j] == 'W':
					new.append([i, j])
					vis[i][j] = True
				if l[i][j] == 'W' or l[i][j] == 'N' or l[i][j] == '.':
					res[i][j] = 0
		dis = 2
		while len(new) > 0:
			size = len(new)
			while size > 0:
				size = size - 1
				k = new.popleft()
				for i in range(4):
					x = k[0] + dx[i]
					y = k[1] + dy[i]
					if x >= 0 and y >= 0 and (x < n) and (y < m) and (vis[x][y] == False) and (l[x][y] != 'N'):
						vis[x][y] = True
						new.append([x, y])
						if l[x][y] == 'H':
							res[x][y] = dis
			dis = dis + 2
		return res


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		wells = deque()
		ans = [[-1 for _ in range(m)] for _ in range(n)]
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'N' or c[i][j] == '.' or c[i][j] == 'W':
					ans[i][j] = 0
				if c[i][j] == 'W':
					wells.append((i, j, 0))
		directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
		while wells:
			(x, y, steps) = wells.popleft()
			for (i, j) in directions:
				new_x = x + i
				new_y = y + j
				if new_x >= 0 and new_x < n and (new_y >= 0) and (new_y < m) and (c[new_x][new_y] == 'H' or c[new_x][new_y] == '.'):
					if c[new_x][new_y] == 'H' and ans[new_x][new_y] == -1:
						ans[new_x][new_y] = steps + 2
					wells.append((new_x, new_y, steps + 2))
					c[new_x][new_y] = 'W'
		return ans


from typing import List
import collections

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		vis = [[0 for j in range(m)] for i in range(n)]
		res = [[-1 for j in range(m)] for i in range(n)]
		queue = collections.deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'N':
					res[i][j] = 0
					vis[i][j] = 1
				elif c[i][j] == '.':
					res[i][j] = 0
				elif c[i][j] == 'W':
					queue.append((i, j, 0))
					vis[i][j] = 1
					res[i][j] = 0
		while queue:
			(row, col, d) = queue.popleft()
			direc = [(row, col - 1), (row, col + 1), (row - 1, col), (row + 1, col)]
			for (r1, c1) in direc:
				if r1 >= 0 and r1 < n and (c1 >= 0) and (c1 < m) and (c[r1][c1] == 'H') and (vis[r1][c1] == 0):
					res[r1][c1] = 2 * (d + 1)
					vis[r1][c1] = 1
					queue.append((r1, c1, d + 1))
				elif r1 >= 0 and r1 < n and (c1 >= 0) and (c1 < m) and (c[r1][c1] == '.') and (vis[r1][c1] == 0):
					vis[r1][c1] = 1
					queue.append((r1, c1, d + 1))
		return res


from typing import List

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		ans = [[None for _ in range(m)] for _ in range(n)]
		well = []
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					well.append([i, j])
					ans[i][j] = 0

		def fun2(row, col):
			if row < 0 or row > n - 1 or col < 0 or (col > m - 1) or ans[row][col] or (c[row][col] == 'N') or (c[row][col] == 'W'):
				return False
			return True

		def fun(bbb):
			ansReturn = []
			for aaa in bbb:
				row = aaa[0]
				col = aaa[1]
				if fun2(row - 1, col):
					ans[row - 1][col] = ans[row][col] + 1
					ansReturn.append([row - 1, col])
				if fun2(row, col - 1):
					ans[row][col - 1] = ans[row][col] + 1
					ansReturn.append([row, col - 1])
				if fun2(row, col + 1):
					ans[row][col + 1] = ans[row][col] + 1
					ansReturn.append([row, col + 1])
				if fun2(row + 1, col):
					ans[row + 1][col] = ans[row][col] + 1
					ansReturn.append([row + 1, col])
			return ansReturn
		while well:
			well = fun(well)
		finalAns = []
		a = 0
		for i in ans:
			b = 0
			p = []
			for j in i:
				if c[a][b] == '.':
					p.append(0)
				elif j == None:
					if c[a][b] == 'N':
						p.append(0)
					else:
						p.append(-1)
				else:
					p.append(j * 2)
				b += 1
			finalAns.append(p)
			a += 1
		return finalAns


from typing import List
from collections import deque

class Solution:
	dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]

	def areCoordinatesValid(self, row, col, n, m):
		return row >= 0 and row < n and (col >= 0) and (col < m)

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		output = [[0 for j in range(m)] for i in range(n)]
		queue = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					queue.append([0, i, j])
		while queue:
			size = len(queue)
			while size > 0:
				curr = queue.popleft()
				(row, col, dist) = (curr[1], curr[2], curr[0])
				for dir in self.dirs:
					(nRow, nCol) = (row + dir[0], col + dir[1])
					if self.areCoordinatesValid(nRow, nCol, n, m) and output[nRow][nCol] == 0 and (c[nRow][nCol] != 'N') and (c[nRow][nCol] != 'W'):
						queue.append([dist + 1, nRow, nCol])
						output[nRow][nCol] = dist + 1
				size -= 1
		for i in range(n):
			for j in range(m):
				if c[i][j] == '.':
					output[i][j] = 0
				elif c[i][j] == 'H':
					if output[i][j] == 0:
						output[i][j] = -1
					else:
						output[i][j] = 2 * output[i][j]
		return output


import math
from collections import deque
from typing import List

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:

		def check_index(x, y):
			if x < 0 or x >= n or y < 0 or (y >= m):
				return False
			if c[x][y] == 'N' or c[x][y] == 'W':
				return False
			return True
		wells = []
		flag = False
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					wells.append((i, j))
		sol = [[-2] * m for _ in range(n)]
		queue = deque()
		for well in wells:
			queue.append(well)
		dist = 0
		while queue:
			k = len(queue)
			for _ in range(k):
				(x, y) = queue.popleft()
				if c[x][y] != 'N':
					if c[x][y] == 'H':
						sol[x][y] = 2 * dist
					c[x][y] = 'N'
					if check_index(x - 1, y):
						queue.append([x - 1, y])
					if check_index(x + 1, y):
						queue.append([x + 1, y])
					if check_index(x, y - 1):
						queue.append([x, y - 1])
					if check_index(x, y + 1):
						queue.append([x, y + 1])
			dist += 1
		for i in range(n):
			for j in range(m):
				if sol[i][j] == -2:
					if c[i][j] == 'H':
						sol[i][j] = -1
					else:
						sol[i][j] = 0
		return sol


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		visited = []
		q = deque()
		ans = []
		for i in range(n):
			l = []
			k1 = []
			for j in range(m):
				l.append(0)
				k1.append(0)
			visited.append(l)
			ans.append(k1)
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					visited[i][j] = 1
					ans[i][j] = 0
					q.append([0, i, j])
		while len(q) != 0:
			(steps, x, y) = q.popleft()
			if y - 1 >= 0 and visited[x][y - 1] != 1 and (c[x][y - 1] == 'H' or c[x][y - 1] == '.'):
				visited[x][y - 1] = 1
				ans[x][y - 1] = steps + 2
				q.append([steps + 2, x, y - 1])
			if y + 1 <= m - 1 and visited[x][y + 1] != 1 and (c[x][y + 1] == 'H' or c[x][y + 1] == '.'):
				visited[x][y + 1] = 1
				ans[x][y + 1] = steps + 2
				q.append([steps + 2, x, y + 1])
			if x - 1 >= 0 and visited[x - 1][y] != 1 and (c[x - 1][y] == 'H' or c[x - 1][y] == '.'):
				visited[x - 1][y] = 1
				ans[x - 1][y] = steps + 2
				q.append([steps + 2, x - 1, y])
			if x + 1 <= n - 1 and visited[x + 1][y] != 1 and (c[x + 1][y] == 'H' or c[x + 1][y] == '.'):
				visited[x + 1][y] = 1
				ans[x + 1][y] = steps + 2
				q.append([steps + 2, x + 1, y])
		for i in range(n):
			for j in range(m):
				if visited[i][j] == 0 and c[i][j] == 'H':
					ans[i][j] = -1
				if c[i][j] == '.':
					ans[i][j] = 0
		return ans


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		ans = [[-1 for _ in range(m)] for _ in range(n)]
		visited = [[False for _ in range(m)] for _ in range(n)]
		queue = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					queue.append((i, j, 0))
					visited[i][j] = True
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		while queue:
			(x, y, z) = queue.popleft()
			ans[x][y] = z
			for u in range(4):
				n_x = x + dx[u]
				n_y = y + dy[u]
				if n_x >= 0 and n_x < n and (n_y >= 0) and (n_y < m) and (visited[n_x][n_y] == False) and (c[n_x][n_y] == 'H' or c[n_x][n_y] == '.'):
					queue.append((n_x, n_y, z + 2))
					visited[n_x][n_y] = True
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'N' or c[i][j] == '.':
					ans[i][j] = 0
		return ans


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					c[i][j] = 0
					q.append((i, j, 0))
		while q:
			(i, j, dist) = q.popleft()
			if c[i][j] == 'HH':
				c[i][j] = dist
			elif c[i][j] == '..':
				c[i][j] = 0
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= x and x <= n - 1 and (0 <= y) and (y <= m - 1):
					if c[x][y] == 'H' or c[x][y] == '.':
						c[x][y] += c[x][y]
						q.append((x, y, dist + 2))
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'N' or c[i][j] == '.':
					c[i][j] = 0
				elif c[i][j] == 'H':
					c[i][j] = -1
		return c


from typing import List
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		visit = [[10 ** 10] * m for _ in range(n)]
		dq = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					dq.append([(i, j), 0])
					visit[i][j] = 0
		lst = [1, -1, 0, 0]
		lst_2 = [0, 0, -1, 1]
		while dq:
			t = dq.popleft()
			(r, c1) = t[0]
			mt = t[1]
			for i in range(4):
				nr = r + lst[i]
				nc = c1 + lst_2[i]
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (c[nr][nc] == 'H' or c[nr][nc] == '.'):
					if visit[nr][nc] > mt + 2:
						visit[nr][nc] = mt + 2
						dq.append([(nr, nc), mt + 2])
		for i in range(n):
			for j in range(m):
				if c[i][j] == '.' or c[i][j] == 'N':
					visit[i][j] = 0
				if visit[i][j] == 10 ** 10:
					visit[i][j] = -1
		return visit


from collections import deque
from typing import List

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		dist = [[-1 for j in range(m)] for i in range(n)]
		Q = deque([(x, y) for x in range(n) for y in range(m) if c[x][y] == 'W'])
		for (x, y) in Q:
			dist[x][y] = 0
		while Q:
			(x, y) = Q.pop()
			for (nx, ny) in [(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]:
				if 0 <= nx < n and 0 <= ny < m and (dist[nx][ny] == -1) and (c[nx][ny] != 'N'):
					dist[nx][ny] = dist[x][y] + 2
					Q.appendleft((nx, ny))
		for x in range(n):
			for y in range(m):
				if c[x][y] in ['N', '.']:
					dist[x][y] = 0
		return dist


from typing import List
from collections import deque
INF = float('inf')

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		visit = [[INF] * m for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					q.append(((i, j), 0))
					visit[i][j] = 0
		dirs = {(1, 0), (-1, 0), (0, 1), (0, -1)}
		while q:
			((r, c1), tim) = q.popleft()
			for (dr, dc) in dirs:
				(nr, nc) = (r + dr, c1 + dc)
				if 0 <= nr < n and 0 <= nc < m and (c[nr][nc] in ('H', '.')):
					if visit[nr][nc] > tim + 2:
						visit[nr][nc] = tim + 2
						q.append(((nr, nc), tim + 2))
		for i in range(n):
			for j in range(m):
				if c[i][j] in ('.', 'N'):
					visit[i][j] = 0
				if visit[i][j] == INF:
					visit[i][j] = -1
		return visit


from typing import List, Tuple
from collections import deque

class Solution:

	def chefAndWells(self, n: int, m: int, c: List[List[str]]) -> List[List[int]]:
		ans = [[-1 for _ in range(m)] for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'W':
					q.append((i, j))
					ans[i][j] = 0
		x = [-1, 1, 0, 0]
		y = [0, 0, -1, 1]
		while q:
			temp = q.popleft()
			(i, j) = (temp[0], temp[1])
			for k in range(4):
				newi = i + x[k]
				newj = j + y[k]
				if 0 <= newi < n and 0 <= newj < m and (c[newi][newj] != 'N') and (ans[newi][newj] == -1):
					ans[newi][newj] = ans[i][j] + 1
					q.append((newi, newj))
		for i in range(n):
			for j in range(m):
				if c[i][j] == 'N' or c[i][j] == '.':
					ans[i][j] = 0
				elif ans[i][j] != -1:
					ans[i][j] *= 2
		return ans