You are given an n x n integer matrix grid where each value grid[i][j] represents height of the cell (i, j).
You can travel from a cell to another 4-directionally adjacent cell if and only the height of the both cells are at most T. You can travel infinite distances in zero time but you must stay within the boundaries of the grid during your travel.
You are currently at cell (0 , 0) and the value of T is 0.and you wish to go to cell (n-1,m-1).
Find the minimum time it will take to reach the cell (n, m) if the value of T increase by 1 every second.
 
Example 1:
Input:
2
0 2
1 3
Output:
3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When time T is 3, we can swim anywhere inside the grid.
 
Example 2:
Input:
4
0 1 2 4
12 13 14 9
15 5 11 10
3 6 7 8 
Output:
10
 
Your Task:
You don't need to read or print anything. Your task is to complete the function Solve() which takes an integer n denoting no. of rows and columns of the grid and a matrix grid[][] denoting the grid and return the maximum group of connected group of 1s.
 
Constraints:
	1 <= n<= 50
	0 <= grid[i][j] 
	Each values in grid is unique

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3



class Solution:

    def Solve(self, n, adj):

        # Code here

Solutions:
import heapq

class Solution:

	def Solve(self, n, grid):
		hp = []
		ans = grid[0][0]
		heapq.heappush(hp, [grid[0][0], 0, 0])
		dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		vis = set()
		vis.add((0, 0))
		while hp:
			(t, i, j) = heapq.heappop(hp)
			ans = max(t, ans)
			if i == n - 1 and j == n - 1:
				return ans
			for (d1, d2) in dir:
				x = i + d1
				y = j + d2
				if x < n and x >= 0 and (y < n) and (y >= 0) and ((x, y) not in vis):
					vis.add((x, y))
					heapq.heappush(hp, [grid[x][y], x, y])


import heapq

class Solution:

	def Solve(self, n, grid):
		rows = len(grid)
		cols = len(grid[0])
		heap = []
		visited = set()
		heapq.heappush(heap, [grid[0][0], 0, 0])
		visited.add((0, 0))
		while heap:
			(time, row, col) = heapq.heappop(heap)
			if row == rows - 1 and col == cols - 1:
				return time
			for (nextr, nextc) in [[-1 + row, col], [1 + row, col], [row, -1 + col], [row, 1 + col]]:
				if 0 <= nextr < rows and 0 <= nextc < cols and ((nextr, nextc) not in visited):
					visited.add((nextr, nextc))
					heapq.heappush(heap, [max(time, grid[nextr][nextc]), nextr, nextc])


import heapq

class Solution:

	def Solve(self, n, grid):
		DIR = [0, -1, 0, 1, 0]
		vis = set((0, 0))

		def isValid(r, c):
			if r >= 0 and r < n and (c >= 0) and (c < n):
				return True
			return False
		queue = [(grid[0][0], 0, 0)]
		while queue:
			(hei, row, col) = heapq.heappop(queue)
			if row == n - 1 and col == n - 1:
				return hei
			for i in range(4):
				(nrow, ncol) = (row + DIR[i], col + DIR[i + 1])
				if isValid(nrow, ncol) and (nrow, ncol) not in vis:
					heapq.heappush(queue, (max(hei, grid[nrow][ncol]), nrow, ncol))
					vis.add((nrow, ncol))


import heapq

class Solution:

	def Solve(self, n, grid):
		m = len(grid)
		n = len(grid[0])
		hp = []
		par = [x for x in range(m * n)]
		size = [1 for _ in range(m * n)]
		dictio = {(1, 0), (0, 1), (-1, 0), (0, -1)}

		def findPar(u):
			if u != par[u]:
				par[u] = findPar(par[u])
				return par[u]
			else:
				return u

		def union(u, v):
			pu = findPar(u)
			pv = findPar(v)
			if size[pu] >= size[pv]:
				size[pu] += size[pv]
				par[pv] = pu
			else:
				size[pv] += size[pu]
				par[pu] = pv
		for i in range(m):
			for j in range(n):
				heapq.heappush(hp, (grid[i][j], i, j))
		while hp:
			(us_height, x, y) = heapq.heappop(hp)
			for (di, dj) in dictio:
				(n_i, n_j) = (x + di, y + dj)
				if n_i >= 0 and n_i < m and (n_j >= 0) and (n_j < n) and (grid[n_i][n_j] < us_height):
					node_no = x * m + y
					adjel_no = n_i * m + n_j
					union(node_no, adjel_no)
			if findPar(0) == findPar(m * n - 1):
				return us_height


from heapq import heappop, heappush

class Solution:

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

	def Solve(self, n, grid):
		pq = [[grid[0][0], [0, 0]]]
		dr = [-1, 0, 1, 0]
		dc = [0, -1, 0, 1]
		ans = 0
		vis = [[0 for i in range(n)] for j in range(n)]
		vis[0][0] = 1
		while pq:
			top = heappop(pq)
			h = top[0]
			row = top[1][0]
			col = top[1][1]
			if row == n - 1 and col == n - 1:
				ans = h
				break
			for i in range(4):
				adjr = row + dr[i]
				adjc = col + dc[i]
				if self.isValid(adjr, adjc, n, n) and vis[adjr][adjc] == 0:
					heappush(pq, [max(h, grid[adjr][adjc]), [adjr, adjc]])
					vis[adjr][adjc] = 1
		return ans


import heapq

class Solution:

	def Solve(self, n, adj):
		pq = [(adj[0][0], 0, 0)]
		maxi = 0
		dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		visited = [[0] * n for _ in range(n)]
		while pq:
			(dis, i, j) = heapq.heappop(pq)
			maxi = max(maxi, dis)
			visited[i][j] = 1
			if i == n - 1 and j == n - 1:
				return maxi
			for (delRow, delCol) in dirc:
				nr = delRow + i
				nc = delCol + j
				if nr >= 0 and nr < n and (nc >= 0) and (nc < n) and (not visited[nr][nc]):
					heapq.heappush(pq, (adj[nr][nc], nr, nc))
		return maxi


import sys
import heapq

class Solution:

	def Solve(self, n, adj):
		n = len(adj)
		m = len(adj[0])
		minheap = []
		time = [[sys.maxsize for i in range(m)] for j in range(n)]
		time[0][0] = adj[0][0]
		heapq.heappush(minheap, [time[0][0], [0, 0]])
		while len(minheap) > 0:
			ele = heapq.heappop(minheap)
			diff = ele[0]
			row = ele[1][0]
			col = ele[1][1]
			delrow = [-1, 0, 1, 0]
			delcol = [0, 1, 0, -1]
			for i in range(0, 4):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (adj[nrow][ncol] < time[nrow][ncol]):
					if diff < adj[nrow][ncol]:
						time[nrow][ncol] = adj[nrow][ncol]
						heapq.heappush(minheap, [time[nrow][ncol], [nrow, ncol]])
					elif diff < time[nrow][ncol]:
						time[nrow][ncol] = diff
						heapq.heappush(minheap, [time[nrow][ncol], [nrow, ncol]])
		return time[n - 1][m - 1]


import heapq

class Solution:

	def Solve(self, n, grid):
		n = len(grid)
		visit = set()
		minH = [[grid[0][0], 0, 0]]
		visit.add((0, 0))
		directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while minH:
			(t, r, c) = heapq.heappop(minH)
			if r == n - 1 and c == n - 1:
				return t
			for (dr, dc) in directions:
				(neiR, neiC) = (r + dr, c + dc)
				if neiR in range(n) and neiC in range(n) and ((neiR, neiC) not in visit):
					visit.add((neiR, neiC))
					heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])


import heapq

class Solution:

	def Solve(self, n, grid):
		vis = set()
		heap = []
		heapq.heappush(heap, (grid[0][0], 0, 0))
		vis.add((0, 0))
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		while heap:
			(time, r, c) = heapq.heappop(heap)
			if r == n - 1 and c == n - 1:
				return time
			for i in range(4):
				nr = r + dx[i]
				nc = c + dy[i]
				if nr >= 0 and nr < n and (nc >= 0) and (nc < n) and ((nr, nc) not in vis):
					vis.add((nr, nc))
					heapq.heappush(heap, (max(time, grid[nr][nc]), nr, nc))