Given a grid of dimension nxm where each cell in the grid can have values 0, 1 or 2 which has the following meaning:
0 : Empty cell 
1 : Cells have fresh oranges 
2 : Cells have rotten oranges 
We have to determine what is the minimum time required to rot all oranges. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. 
 
Example 1:
Input: grid = {{0,1,2},{0,1,2},{2,1,1}}
Output: 1
Explanation: The grid is-
0 1 2
0 1 2
2 1 1
Oranges at positions (0,2), (1,2), (2,0)
will rot oranges at (0,1), (1,1), (2,2) and 
(2,1) in unit time.
Example 2:
Input: grid = {{2,2,0,1}}
Output: -1
Explanation: The grid is-
2 2 0 1
Oranges at (0,0) and (0,1) can't rot orange at
(0,3).
 
Your Task:
You don't need to read or print anything, Your task is to complete the function orangesRotting() which takes grid as input parameter and returns the minimum time to rot all the fresh oranges. If not possible returns -1.
 
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
 
Constraints:
1 ≤ n, m ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Graph algorithms

Data structures

Starter code: class Solution:



    #Function to find minimum time required to rot all oranges. 

	def orangesRotting(self, grid):

		#Code here

Solutions:
class Solution:

	def orangesRotting(self, grid):
		q = []
		(m, n) = (len(grid), len(grid[0]))
		count_oranges = 0
		grid1 = grid
		for i in range(m):
			for j in range(n):
				if grid1[i][j] == 2:
					q.append((i, j))
				if grid1[i][j] == 1:
					count_oranges += 1
		if count_oranges == 0:
			return 0
		if not q:
			return -1
		dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		min = 0
		while q:
			size = len(q)
			while size > 0:
				(x, y) = q.pop(0)
				size -= 1
				for (x1, y1) in dir:
					(i, j) = (x + x1, y + y1)
					if 0 <= i < m and 0 <= j < n and (grid1[i][j] == 1):
						grid1[i][j] = 2
						count_oranges -= 1
						q.append((i, j))
			min += 1
			if count_oranges == 0:
				return min
		return -1


class Solution:

	def orangesRotting(self, a):
		q = []
		n = len(a)
		m = len(a[0])
		for i in range(n):
			for j in range(m):
				if a[i][j] == 2:
					q.append((i, j, 0))
		ans = 0
		while len(q) > 0:
			l = len(q)
			for i in range(l):
				(i, j, t) = q[0]
				q.pop(0)
				ans = max(ans, t)
				if i + 1 <= n - 1 and a[i + 1][j] == 1:
					q.append((i + 1, j, t + 1))
					a[i + 1][j] = 2
				if i - 1 >= 0 and a[i - 1][j] == 1:
					q.append((i - 1, j, t + 1))
					a[i - 1][j] = 2
				if j + 1 <= m - 1 and a[i][j + 1] == 1:
					q.append((i, j + 1, t + 1))
					a[i][j + 1] = 2
				if j - 1 >= 0 and a[i][j - 1] == 1:
					q.append((i, j - 1, t + 1))
					a[i][j - 1] = 2
		for i in range(n):
			for j in range(m):
				if a[i][j] == 1:
					return -1
		return ans


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for _ in range(m)] for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					q.append(((i, j), 0))
					visited[i][j] = 2
		tm = 0
		drow = [-1, 0, 1, 0]
		dcol = [0, -1, 0, 1]
		while q:
			((r, c), t) = q.popleft()
			tm = max(tm, t)
			for i in range(4):
				nrow = r + drow[i]
				ncol = c + dcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] != 2) and (grid[nrow][ncol] == 1):
					q.append(((nrow, ncol), t + 1))
					visited[nrow][ncol] = 2
		for i in range(n):
			for j in range(m):
				if visited[i][j] != 2 and grid[i][j] == 1:
					return -1
		return tm


class Solution:

	def orangesRotting(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[0] * m for i in grid]
		q = []
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					q.append([[i, j], 0])
					visited[i][j] = 2
		tm = 0
		row = [-1, 0, 1, 0]
		col = [0, 1, 0, -1]
		while q:
			sr = q[0][0][0]
			sc = q[0][0][1]
			t = q[0][1]
			tm = max(tm, t)
			q.pop(0)
			for i in range(4):
				nrow = sr + row[i]
				ncol = sc + col[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] != 2) and (grid[nrow][ncol] == 1):
					q.append([[nrow, ncol], t + 1])
					visited[nrow][ncol] = 2
		for i in range(n):
			for j in range(m):
				if visited[i][j] != 2 and grid[i][j] == 1:
					return -1
		return tm


class Solution:

	def orangesRotting(self, grid):

		def do(i, j, temp):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])):
				return
			if grid[i][j] == 1:
				grid[i][j] += 1
				temp.append([i, j])
		rotten = []
		temp = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 2:
					temp.append([i, j])
		rotten.append(temp)
		count = 0
		while len(rotten) > 0:
			temp = []
			for i in rotten[0]:
				do(i[0] - 1, i[1], temp)
				do(i[0] + 1, i[1], temp)
				do(i[0], i[1] + 1, temp)
				do(i[0], i[1] - 1, temp)
			if temp != []:
				rotten.append(temp)
				count += 1
				temp = []
			rotten.pop(0)
		for i in grid:
			for j in i:
				if j == 1:
					return -1
		return count if count > 0 else -1


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		n = len(grid)
		m = len(grid[0])
		queue = deque()
		fresh_count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					queue.append((i, j, 0))
				elif grid[i][j] == 1:
					fresh_count += 1
		if fresh_count == 0:
			return 0
		directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		while queue:
			(row, col, time) = queue.popleft()
			for (dx, dy) in directions:
				new_row = row + dx
				new_col = col + dy
				if 0 <= new_row < n and 0 <= new_col < m and (grid[new_row][new_col] == 1):
					grid[new_row][new_col] = 2
					queue.append((new_row, new_col, time + 1))
					fresh_count -= 1
					if fresh_count == 0:
						return time + 1
		return -1


from queue import Queue

class Solution:

	def orangesRotting(self, grid):
		m = len(grid)
		n = len(grid[0])
		q = Queue()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 2:
					q.put([i, j])
		res = 0
		size = q.qsize()
		while size > 0:
			for _ in range(size):
				topNode = q.get()
				deltaRow = [-1, 0, 1, 0]
				deltaCol = [0, 1, 0, -1]
				for i in range(4):
					r = topNode[0] + deltaRow[i]
					c = topNode[1] + deltaCol[i]
					if ((r >= 0 and r < m) and (c >= 0 and c < n)) and grid[r][c] == 1:
						grid[r][c] = 2
						q.put([r, c])
			size = q.qsize()
			if size > 0:
				res += 1
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					return -1
		return res


class Solution:

	def orangesRotting(self, grid):
		n = len(grid)
		m = len(grid[0])
		s = []
		cntfresh = 0
		vis = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					s.append([i, j, 0])
					vis[i][j] = 2
				if grid[i][j] == 1:
					cntfresh += 1
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		count = 0
		total = 0
		while len(s) > 0:
			(i, j, t) = s.pop(0)
			count = max(count, t)
			for x in range(4):
				ni = i + dx[x]
				nj = j + dy[x]
				if ni >= 0 and ni < n and (nj >= 0) and (nj < m) and (vis[ni][nj] != 2) and (grid[ni][nj] == 1):
					s.append([ni, nj, t + 1])
					vis[ni][nj] = 2
					total += 1
		if cntfresh != total:
			return -1
		else:
			return count


from collections import deque
import itertools

class Solution:

	def orangesRotting(self, grid):
		n = len(grid)
		m = len(grid[0])
		delRow = [-1, 0, +1, 0]
		delCol = [0, +1, 0, -1]
		totalFreshOrange = 0
		totalBFSFreshOrange = 0
		visited = [[None for _ in range(m)] for _ in range(n)]
		q = deque()
		for (row, col) in itertools.product(range(n), range(m)):
			if grid[row][col] == 2:
				q.append((row, col, 0))
			if grid[row][col] == 1:
				totalFreshOrange += 1
		timeRequired = 0
		while q:
			(newRow, newCol, time) = q.popleft()
			timeRequired = max(timeRequired, time)
			visited[newRow][newCol] = 1
			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] == 1) and (visited[nRow][nCol] is None):
					totalBFSFreshOrange += 1
					visited[nRow][nCol] = 1
					q.append((nRow, nCol, time + 1))
		if totalBFSFreshOrange != totalFreshOrange:
			return -1
		return timeRequired


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		(time, freshOranges) = (0, 0)
		q = deque()
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] == 1:
					freshOranges += 1
				if grid[r][c] == 2:
					q.append([r, c])
		directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while q and freshOranges > 0:
			for i in range(len(q)):
				(r, c) = q.popleft()
				for (dr, dc) in directions:
					(row, col) = (dr + r, dc + c)
					if row < 0 or row == len(grid) or col < 0 or (col == len(grid[0])) or (grid[row][col] != 1):
						continue
					grid[row][col] = 2
					q.append([row, col])
					freshOranges -= 1
			time += 1
		return time if freshOranges == 0 else -1


import queue

class Solution:

	def orangesRotting(self, grid):
		q = queue.Queue()
		nonEmptyCells = 0
		rottenCells = 0
		freshCells = 0
		minutes = 0
		row = len(grid)
		col = len(grid[0])
		for i in range(row):
			for j in range(col):
				if grid[i][j] != 0:
					nonEmptyCells += 1
				if grid[i][j] == 2:
					q.put([i, j])
					rottenCells += 1
		row_dirs = [-1, 0, 1, 0]
		col_dirs = [0, -1, 0, 1]
		while not q.empty():
			qLen = q.qsize()
			flag = False
			for p in range(qLen):
				curr = q.get()
				curr_row = curr[0]
				curr_col = curr[1]
				for dir in range(4):
					x = curr_row + row_dirs[dir]
					y = curr_col + col_dirs[dir]
					if x >= 0 and x < row and (y >= 0) and (y < col) and (grid[x][y] == 1):
						grid[x][y] = 2
						q.put([x, y])
						freshCells += 1
						flag = True
			if flag:
				minutes += 1
		if nonEmptyCells - rottenCells == freshCells:
			return minutes
		return -1


class Solution:

	def orangesRotting(self, grid):
		arr = grid
		que = []
		l = len(arr[0])
		for i in range(len(arr)):
			for j in range(l):
				if arr[i][j] == 2:
					que.append([i, j, 0])
				else:
					continue
		t = 0
		while que:
			(i, j, t) = que.pop(0)
			for (r, c) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
				if 0 <= r < len(arr) and 0 <= c < l and (arr[r][c] == 1):
					arr[r][c] = 2
					que.append([r, c, t + 1])
		return -1 if any((c == 1 for r in arr for c in r)) else t


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		q = deque()
		visited = set()
		n = len(grid)
		m = len(grid[0])
		countfresh = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					visited.add((i, j))
					q.append((i, j, 0))
				if grid[i][j] == 1:
					countfresh += 1
		timer = 0
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		cnt = 0
		while q:
			(r, c, t) = q.popleft()
			timer = max(t, timer)
			for i in range(4):
				nextr = r + drow[i]
				nextc = c + dcol[i]
				if nextr >= 0 and nextr < n and (nextc >= 0) and (nextc < m) and ((nextr, nextc) not in visited) and (grid[nextr][nextc] == 1):
					visited.add((nextr, nextc))
					q.append((nextr, nextc, t + 1))
					cnt += 1
		if cnt != countfresh:
			return -1
		return timer


class Solution:

	def orangesRotting(self, grid):

		def fun(grid):
			n = len(grid)
			m = len(grid[0])
			queue = []
			visited = [[0 for i in range(m)] for j in range(n)]
			for i in range(n):
				for j in range(m):
					if grid[i][j] == 2:
						queue.append(((i, j), 0))
						visited[i][j] = 2
			time = 0
			drow = [-1, 0, 1, 0]
			dcol = [0, 1, 0, -1]
			while len(queue) > 0:
				r = queue[0][0][0]
				c = queue[0][0][1]
				t = queue[0][1]
				time = max(time, t)
				queue.pop(0)
				for i in range(4):
					nrow = r + drow[i]
					ncol = c + dcol[i]
					if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] != 2) and (grid[nrow][ncol] == 1):
						queue.append(((nrow, ncol), t + 1))
						visited[nrow][ncol] = 2
			for i in range(n):
				for j in range(m):
					if visited[i][j] != 2 and grid[i][j] == 1:
						return -1
			return time
		return fun(grid)


class Solution:

	def orangesRotting(self, grid):
		row = len(grid)
		col = len(grid[0])
		vis = [[0 for j in range(col)] for i in range(row)]
		q = []
		time = 0
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 2:
					q.append((i, j, 0))
					vis[i][j] = 2
		while q:
			(r, c, t) = q.pop(0)
			time = max(time, t)
			for i in range(4):
				nrow = r + dr[i]
				ncol = c + dc[i]
				if nrow >= 0 and ncol >= 0 and (ncol < col) and (nrow < row) and (grid[nrow][ncol] == 1) and (vis[nrow][ncol] == 0):
					vis[nrow][ncol] = 2
					q.append((nrow, ncol, t + 1))
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1 and vis[i][j] != 2:
					return -1
		return time


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		r = len(grid)
		c = len(grid[0])
		fresh = count = 0
		q = deque()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					fresh += 1
				if grid[i][j] == 2:
					q.append((i, j, 0))
		while q and count >= 0:
			(i, j, count) = q.popleft()
			for (x, y) in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
				if x >= 0 and y >= 0 and (x < n) and (y < m) and (grid[x][y] == 1):
					q.append((x, y, count + 1))
					grid[x][y] = 2
					fresh -= 1
		if fresh == 0:
			return count
		else:
			return -1


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		(row, col) = ([0, -1, 0, 1], [-1, 0, 1, 0])
		visited = []
		lvl = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					visited.append([i, j, lvl])
		return self.bfs(grid, n, m, row, col, visited)

	def bfs(self, mat, n, m, row, col, visited):
		q = deque()
		for val in visited:
			q.append(val)
		max_lvl = 0
		while len(q) > 0:
			temp = q.popleft()
			(i, j, lvl) = (temp[0], temp[1], temp[2])
			if mat[i][j] == 2:
				for k in range(len(row)):
					if i + row[k] < 0 or i + row[k] > n - 1 or j + col[k] < 0 or (j + col[k] > m - 1):
						continue
					elif mat[i + row[k]][j + col[k]] == 1:
						mat[i + row[k]][j + col[k]] = 2
						q.append([i + row[k], j + col[k], lvl + 1])
						max_lvl = max(max_lvl, lvl + 1)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					return -1
		return max_lvl


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		vis = [[False for _ in range(n)] for _ in range(m)]
		q = deque()
		cf = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 2:
					q.append([[i, j], 0])
					vis[i][j] = True
				if grid[i][j] == 1:
					cf += 1
		delrow = [-1, 0, 1, 0]
		delcol = [0, -1, 0, 1]
		time = 0
		count = 0
		while len(q):
			x = q.popleft()
			(r, c, t) = (x[0][0], x[0][1], x[1])
			time = max(time, t)
			for i in range(4):
				row = r + delrow[i]
				col = c + delcol[i]
				if row >= 0 and row < len(grid) and (col >= 0) and (col < len(grid[0])) and (grid[row][col] == 1) and (vis[row][col] == False):
					q.append([[row, col], t + 1])
					count += 1
					vis[row][col] = True
		if cf != count:
			return -1
		return time


class Solution:

	def orangesRotting(self, grid):
		n = len(grid)
		m = len(grid[0])
		queue = []
		count_fresh_oranges = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					queue.append((i, j))
				elif grid[i][j] == 1:
					count_fresh_oranges += 1
		time = 0
		while queue:
			level_size = len(queue)
			for i in range(level_size):
				(curr_i, curr_j) = queue.pop(0)
				for (di, dj) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
					(ni, nj) = (curr_i + di, curr_j + dj)
					if ni >= 0 and ni < n and (nj >= 0) and (nj < m) and (grid[ni][nj] == 1):
						grid[ni][nj] = 2
						queue.append((ni, nj))
						count_fresh_oranges -= 1
			time += 1
		if count_fresh_oranges > 0:
			return -1
		else:
			return time - 1


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		visited = [[False if element != 0 else True for element in grid[i]] for i in range(len(grid))]

		def _rot_adj(i, j, grid, queue, count):
			positions = [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]
			for position in positions:
				x = position[0]
				y = position[1]
				if x < 0 or y < 0:
					continue
				try:
					if grid[x][y] == 1 and (not visited[x][y]):
						grid[x][y] = 2
						visited[x][y] = True
						queue.append((x, y, count + 1))
					elif grid[x][y] == 0:
						visited[x][y] = True
				except IndexError:
					pass

		def _add_rotten(grid, queue, count):
			for row in range(0, len(grid)):
				for col in range(0, len(grid[row])):
					if grid[row][col] == 2 and (not visited[row][col]):
						visited[row][col] = True
						queue.append((row, col, count))

		def _is_all_rotten(visited, count):
			for row in range(0, len(visited)):
				for col in range(0, len(visited[row])):
					if visited[row][col] == False:
						return -1
			return count
		count = 0
		queue = deque([])
		_add_rotten(grid, queue, count)
		while queue:
			(i, j, count) = queue.popleft()
			_rot_adj(i, j, grid, queue, count)
		return _is_all_rotten(visited, count)


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		queue = deque()
		fresh_oranges = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 2:
					queue.append((i, j, 0))
				elif grid[i][j] == 1:
					fresh_oranges += 1
		time = 0
		while queue:
			(i, j, time) = queue.popleft()
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (grid[x][y] == 1):
					grid[x][y] = 2
					fresh_oranges -= 1
					queue.append((x, y, time + 1))
		if fresh_oranges == 0:
			return time
		else:
			return -1


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		rows = len(grid)
		cols = len(grid[0])
		queue = deque()
		fresh_oranges = 0
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 2:
					queue.append((i, j))
				elif grid[i][j] == 1:
					fresh_oranges += 1
		if fresh_oranges == 0:
			return 0
		time = 0
		while queue:
			time += 1
			level_size = len(queue)
			for _ in range(level_size):
				(row, col) = queue.popleft()
				for (dx, dy) in directions:
					(new_row, new_col) = (row + dx, col + dy)
					if 0 <= new_row < rows and 0 <= new_col < cols and (grid[new_row][new_col] == 1):
						grid[new_row][new_col] = 2
						fresh_oranges -= 1
						queue.append((new_row, new_col))
		if fresh_oranges > 0:
			return -1
		return time - 1


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visited = [[0 for _ in range(m)] for _ in range(n)]
		q = deque()
		fresh_cnt = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					q.append((i, j, 0))
					visited[i][j] = 1
				elif grid[i][j] == 1:
					fresh_cnt += 1
		tm = 0
		while q:
			(i, j, t) = q.popleft()
			tm = max(tm, t)
			if 0 <= i < n and 0 <= j - 1 < m and (grid[i][j - 1] == 1) and (visited[i][j - 1] == 0):
				q.append((i, j - 1, t + 1))
				grid[i][j - 1] = 2
				visited[i][j - 1] = 1
				fresh_cnt -= 1
			if 0 <= i < n and 0 <= j + 1 < m and (grid[i][j + 1] == 1) and (visited[i][j + 1] == 0):
				q.append((i, j + 1, t + 1))
				grid[i][j + 1] = 2
				visited[i][j + 1] = 1
				fresh_cnt -= 1
			if 0 <= i - 1 < n and 0 <= j < m and (grid[i - 1][j] == 1) and (visited[i - 1][j] == 0):
				q.append((i - 1, j, t + 1))
				grid[i - 1][j] = 2
				visited[i - 1][j] = 1
				fresh_cnt -= 1
			if 0 <= i + 1 < n and 0 <= j < m and (grid[i + 1][j] == 1) and (visited[i + 1][j] == 0):
				q.append((i + 1, j, t + 1))
				grid[i + 1][j] = 2
				visited[i + 1][j] = 1
				fresh_cnt -= 1
		return tm if fresh_cnt == 0 else -1


class Solution:

	def orangesRotting(self, gp):
		d = dict()
		leng = 0
		for i in range(len(gp)):
			for j in range(len(gp[0])):
				d[i, j] = float('inf')
		for i in range(len(gp)):
			for j in range(len(gp[0])):
				if gp[i][j] == 2:
					time = 0
					visted = set()
					d[i, j] = 0
					self.Bfs(i, j, gp, visted, d)
				if gp[i][j] == 1 or gp[i][j] == 2:
					leng += 1
		tl = 0
		for i in range(len(gp)):
			for j in range(len(gp[0])):
				if d[i, j] != float('inf'):
					tl += 1
		if tl == leng:
			m = -1
			for i in d.values():
				if i < float('inf') and i > m:
					m = i
			return m
		return -1

	def safe(self, x, y, gp):
		if x >= 0 and x < len(gp) and (y >= 0) and (y < len(gp[0])) and (gp[x][y] == 1) and (gp[x][y] != 0):
			return True
		return False

	def Bfs(self, i, j, gp, visted, d):
		queue = []
		queue.append((i, j))
		visted.add((i, j))
		while len(queue) != 0:
			(i, j) = queue.pop(0)
			List = [(1, 0), (0, 1), (0, -1), (-1, 0)]
			for (a, b) in List:
				saf = self.safe(i + a, j + b, gp)
				if saf == True and (i + a, j + b) not in visted:
					visted.add((i + a, j + b))
					queue.append((i + a, j + b))
					if d[i, j] + 1 < d[i + a, j + b]:
						d[i + a, j + b] = d[i, j] + 1


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		rows = len(grid)
		if rows == 0:
			return -1
		cols = len(grid[0])
		fresh_cnt = 0
		rotten = deque()
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] == 2:
					rotten.append((r, c))
				elif grid[r][c] == 1:
					fresh_cnt += 1
		minutes_passed = 0
		while rotten and fresh_cnt > 0:
			minutes_passed += 1
			for _ in range(len(rotten)):
				(x, y) = rotten.popleft()
				for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					(xx, yy) = (x + dx, y + dy)
					if xx < 0 or xx == rows or yy < 0 or (yy == cols):
						continue
					if grid[xx][yy] == 0 or grid[xx][yy] == 2:
						continue
					fresh_cnt -= 1
					grid[xx][yy] = 2
					rotten.append((xx, yy))
		return minutes_passed if fresh_cnt == 0 else -1


class Solution:

	def orangesRotting(self, grid):
		ct = 0
		res = -1
		q = Queue()
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					ct += 1
				if grid[i][j] == 2:
					q.put([i, j])
		while not q.empty():
			res += 1
			size = q.qsize()
			for k in range(size):
				cur = q.get()
				ct -= 1
				for i in range(4):
					x = cur[0] + dx[i]
					y = cur[1] + dy[i]
					if x >= len(grid) or x < 0 or y >= len(grid[0]) or (y < 0) or (grid[x][y] != 1):
						continue
					grid[x][y] = 2
					q.put([x, y])
		if ct:
			return -1
		else:
			return max(0, res)


class Solution:

	def orangesRotting(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		queue = []
		fresh_count = 0
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 2:
					queue.append((i, j))
				elif grid[i][j] == 1:
					fresh_count += 1
		directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		time = 0
		while queue:
			if fresh_count == 0:
				return time
			time += 1
			for _ in range(len(queue)):
				(x, y) = queue.pop(0)
				for (dx, dy) in directions:
					(nx, ny) = (x + dx, y + dy)
					if 0 <= nx < rows and 0 <= ny < cols and (grid[nx][ny] == 1):
						grid[nx][ny] = 2
						queue.append((nx, ny))
						fresh_count -= 1
		if fresh_count > 0:
			return -1
		return time


class Solution:

	def orangesRotting(self, grid):
		queue = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 2:
					queue.append((i, j, 0))
		time_taken = 0
		while queue:
			(i, j, time_taken) = queue.pop(0)
			for (ni, nj) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and (grid[ni][nj] == 1):
					grid[ni][nj] = 2
					queue.append((ni, nj, time_taken + 1))
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					return -1
		return time_taken


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		(row, col) = ([0, -1, 0, 1], [-1, 0, 1, 0])
		visited = []
		l = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					visited.append([i, j, l])
		return self.bfs(grid, n, m, row, col, visited)

	def bfs(Self, mat, n, m, row, col, v):
		q = deque()
		for i in v:
			q.append(i)
		max_l = 0
		while len(q) > 0:
			t = q.popleft()
			(i, j, l) = (t[0], t[1], t[2])
			if mat[i][j] == 2:
				for k in range(len(row)):
					if i + row[k] < 0 or i + row[k] > n - 1 or j + col[k] < 0 or (j + col[k] > m - 1):
						continue
					elif mat[i + row[k]][j + col[k]] == 1:
						mat[i + row[k]][j + col[k]] = 2
						q.append([i + row[k], j + col[k], l + 1])
						max_l = max(max_l, l + 1)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					return -1
		return max_l


class Solution:

	def orangesRotting(self, grid):
		from collections import deque
		n = len(grid)
		m = len(grid[0])
		queue = deque()
		fresh_count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					queue.append((i, j))
				elif grid[i][j] == 1:
					fresh_count += 1
		time_taken = 0
		while queue:
			time_taken += 1
			for _ in range(len(queue)):
				(i, j) = queue.popleft()
				for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
					x = i + dx
					y = j + dy
					if 0 <= x < n and 0 <= y < m and (grid[x][y] == 1):
						grid[x][y] = 2
						queue.append((x, y))
						fresh_count -= 1
			if fresh_count == 0:
				return time_taken
		if fresh_count > 0:
			return -1
		else:
			return 0


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		m = len(grid[0])
		n = len(grid)
		q = deque()
		vis = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 2:
					q.append([i, j, 0])
					vis[i][j] = 2
		time = 0
		drow = [-1, 0, +1, 0]
		dcol = [0, -1, 0, +1]
		while q:
			(row, col, t) = q.popleft()
			time = max(time, t)
			for i in range(4):
				nrow = row + drow[i]
				ncol = col + dcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] != 2) and (grid[nrow][ncol] == 1):
					q.append([nrow, ncol, t + 1])
					vis[nrow][ncol] = 2
		for i in range(n):
			for j in range(m):
				if vis[i][j] != 2 and grid[i][j] == 1:
					return -1
		return time


from collections import deque

class Solution:

	def orangesRotting(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		fresh_count = 0
		queue = deque()
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 2:
					queue.append((i, j))
				elif grid[i][j] == 1:
					fresh_count += 1
		if fresh_count == 0:
			return 0
		directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		level = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				(x, y) = queue.popleft()
				for (dx, dy) in directions:
					nx = x + dx
					ny = y + dy
					if 0 <= nx < rows and 0 <= ny < cols and (grid[nx][ny] == 1):
						grid[nx][ny] = 2
						fresh_count -= 1
						queue.append((nx, ny))
			level += 1
		if fresh_count == 0:
			return level - 1
		else:
			return -1


class Solution:

	def orangesRotting(self, a):
		ans = 0
		q = []
		n = len(a)
		m = len(a[0])
		for i in range(n):
			for j in range(m):
				if a[i][j] == 2:
					q.append((i, j, 0))
		while len(q) != 0:
			(row, col, c) = q.pop(0)
			ans = c
			for i in [-1, 1]:
				if row + i >= 0 and row + i < n and (a[row + i][col] == 1):
					a[row + i][col] = 2
					q.append((row + i, col, c + 1))
				if col + i >= 0 and col + i < m and (a[row][col + i] == 1):
					a[row][col + i] = 2
					q.append((row, col + i, c + 1))
		for i in range(n):
			for j in range(m):
				if a[i][j] == 1:
					return -1
		return ans