Given a binary grid of n*m. Find the distance of the nearest 1 in the grid for each cell.
The distance is calculated as |i_{1}  - i_{2}| + |j_{1} - j_{2}|, where i_{1}, j_{1} are the row number and column number of the current cell, and i_{2}, j_{2} are the row number and column number of the nearest cell having value 1. There should be atleast one 1 in the grid.
 
Example 1:
Input: grid = {{0,1,1,0},{1,1,0,0},{0,0,1,1}}
Output: {{1,0,0,1},{0,0,1,1},{1,1,0,0}}
Explanation: The grid is-
0 1 1 0 
1 1 0 0 
0 0 1 1 
0's at (0,0), (0,3), (1,2), (1,3), (2,0) and
(2,1) are at a distance of 1 from 1's at (0,1),
(0,2), (0,2), (2,3), (1,0) and (1,1)
respectively.
Example 2:
Input: grid = {{1,0,1},{1,1,0},{1,0,0}}
Output: {{0,1,0},{0,0,1},{0,1,2}}
Explanation: The grid is-
1 0 1
1 1 0
1 0 0
0's at (0,1), (1,2), (2,1) and (2,2) are at a 
distance of 1, 1, 1 and 2 from 1's at (0,0),
(0,2), (2,0) and (1,1) respectively.
 
Yout Task:
You don't need to read or print anything, Your task is to complete the function nearest() which takes the grid as an input parameter and returns a matrix of the same dimensions where the value at index (i, j) in the resultant matrix signifies the minimum distance of 1 in the matrix from grid[i][j].
 
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1 ≤ n, m ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph algorithms

Graph traversal

Starter code: class Solution:



    #Function to find distance of nearest 1 in the grid for each cell.

	def nearest(self, grid):

		#Code here

Solutions:
class Solution:

	def nearest(self, grid):
		from collections import deque
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for _ in range(n)]
		dist = [[0] * m for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					q.append([[i, j], 0])
					vis[i][j] = 1
				else:
					vis[i][j] = 0
		delrow = [-1, 0, +1, 0]
		delcol = [0, +1, 0, -1]
		while q:
			([row, col], steps) = q.popleft()
			dist[row][col] = steps
			for i in range(4):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if 0 <= nrow < n and 0 <= ncol < m and (vis[nrow][ncol] == 0):
					vis[nrow][ncol] = 1
					q.append([[nrow, ncol], steps + 1])
		return dist


from collections import deque

class Solution:

	def nearest(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for _ in range(m)] for _ in range(n)]
		dis = [[0 for _ in range(m)] for _ in range(n)]
		queue = deque()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					queue.append((i, j, 0))
					visited[i][j] = 1
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		while queue:
			(row, col, steps) = queue.popleft()
			dis[row][col] = steps
			for d in range(4):
				nrow = row + drow[d]
				ncol = col + dcol[d]
				if 0 <= nrow < n and 0 <= ncol < m and (visited[nrow][ncol] == 0):
					visited[nrow][ncol] = 1
					queue.append((nrow, ncol, steps + 1))
		return dis


from collections import deque

class Solution:

	def nearest(self, grid):
		row = len(grid)
		col = len(grid[0])
		vis = [[0 for _ in range(col)] for _ in range(row)]
		dis = [[0 for _ in range(col)] for _ in range(row)]
		q = deque()
		dr = [-1, 0, 1, 0]
		dc = [0, -1, 0, 1]
		for r in range(row):
			for c in range(col):
				if grid[r][c] == 1:
					q.append((r, c, 0))
					vis[r][c] = 1
		while q:
			(r, c, step) = q.popleft()
			dis[r][c] = step
			for k in range(4):
				nrow = r + dr[k]
				ncol = c + dc[k]
				if nrow >= 0 and ncol >= 0 and (nrow < row) and (ncol < col) and (vis[nrow][ncol] == 0):
					vis[nrow][ncol] = 1
					q.append((nrow, ncol, step + 1))
		return dis


from collections import deque

class Solution:

	def nearest(self, grid):
		m = len(grid)
		n = len(grid[0])
		vs = [[0] * n for _ in range(m)]
		q = deque()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					q.append((i, j, 0))
					vs[i][j] = 1
					grid[i][j] = 0
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		while len(q) > 0:
			rp = q.popleft()
			for i in range(4):
				nx = rp[0] + dx[i]
				ny = rp[1] + dy[i]
				if nx >= 0 and nx < m and (ny >= 0) and (ny < n) and (vs[nx][ny] == 0) and (grid[nx][ny] == 0):
					grid[nx][ny] = rp[2] + 1
					vs[nx][ny] = 1
					q.append((nx, ny, rp[2] + 1))
		return grid


import itertools
from collections import deque

class Solution:

	def nearest(self, grid):
		q = deque()
		n = len(grid)
		m = len(grid[0])
		visited = [[None for _ in range(m)] for _ in range(n)]
		result = [[0 for _ in range(m)] for _ in range(n)]
		delRow = [-1, 0, +1, 0]
		delCol = [0, +1, 0, -1]
		for (row, col) in itertools.product(range(n), range(m)):
			if grid[row][col] == 1:
				q.append((row, col, 0))
		while q:
			(newRow, newCol, steps) = q.popleft()
			visited[newRow][newCol] = 1
			result[newRow][newCol] = steps
			for i in range(4):
				nRow = newRow + delRow[i]
				nCol = newCol + delCol[i]
				if nRow >= 0 and nRow < n and (nCol >= 0) and (nCol < m) and (grid[nRow][nCol] == 0) and (visited[nRow][nCol] is None):
					visited[nRow][nCol] = 1
					q.append((nRow, nCol, steps + 1))
		return result


from collections import deque

class Solution:

	def nearest(self, arr):
		q = deque()
		n = len(arr)
		m = len(arr[0])
		dist = [[0 for i in range(m)] for j in range(n)]
		visited = set()
		for i in range(n):
			for j in range(m):
				if arr[i][j] == 1:
					q.append((i, j, 0))
					visited.add((i, j))
		while q:
			(row, col, d) = q.popleft()
			dist[row][col] = d
			disi = [1, -1, 0, 0]
			disj = [0, 0, 1, -1]
			for i in range(4):
				nextr = row + disi[i]
				nextc = col + disj[i]
				if nextr >= 0 and nextr < n and (nextc >= 0) and (nextc < m) and ((nextr, nextc) not in visited):
					visited.add((nextr, nextc))
					q.append((nextr, nextc, d + 1))
		return dist


from collections import deque

class Solution:

	def nearest(self, grid):
		q = deque([])
		rows = len(grid)
		cols = len(grid[0])
		distance = [['.'] * cols for i in range(rows)]
		visited = set()
		directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 1:
					visited.add((i, j))
					q.append(((i, j), 0))
					distance[i][j] = 0
		while q:
			((r, c), step) = q.popleft()
			for (dr, dc) in directions:
				row = r + dr
				col = c + dc
				if row not in range(rows) or col not in range(cols) or (row, col) in visited or (grid[row][col] == 1):
					continue
				distance[row][col] = step + 1
				visited.add((row, col))
				q.append(((row, col), step + 1))
		return distance