Geeks Island is represented by an N * M matrix mat. The island is touched by the Indian Ocean from the top and left edges and the Arabian Sea from the right and bottom edges. Each element of the matrix represents the height of the cell.
Due to the rainy season, the island receives a lot of rainfall, and the water can flow in four directions(up, down, left, or right) from one cell to another one with height equal or lower.
You need to find the number of cells from where water can flow to both the Indian Ocean and the Arabian Sea.
Example 1:
Input:
N = 5, M = 5
mat[][] =    {{1, 3, 3, 2, 4},
               {4, 5, 6, 4, 4},
               {2, 4, 5, 3, 1},
               {6, 7, 1, 4, 5},
               {6, 1, 1, 3, 4}}
Output:
8
Explanation:
Indian    ~   ~   ~   ~   ~
Ocean  ~  1   3   3   2  (4) *
        ~  4   5  (6) (4) (4) *
        ~  2   4  (5)  3   1  *
        ~ (6) (7)  1   4   5  *
        ~ (6)  1   1   3   4  *           
           *   *   *   *   * Arabian Sea
Water can flow to both ocean and sea from the cells
denoted by parantheses().For example at index(1,2), the height of that island is 6. If a water drop falls on that island, water can flow to up direction(as 3<=6) and reach to Indian Ocean. ALso, water can flow to right direction(as 6>=4>=4) and reach to Arabian Sea.
Example 2:
Input:
N = 2, M = 3
mat[][] =    {{1, 1, 1},
               {1, 1, 1}}
Output:
6 
Explanation:
Water can flow from all cells to both Indian Ocean and Arabian Sea as the height of all islands are same.
Your Task:
Your task is to complete the function water_flow() which takes an integer array mat, integer N and integer M as the input parameter and returns an integer, denoting the number of cells from which water can to both ocean and sea.
Expected Time Complexity : O(N*M)
Expected Auxiliary Space : O(N*M)
Constraints:
	1 <= N, M <= 10^{3}
	1 <= mat[i][j] <= 10^{6}

Difficulty: MEDIUM
Tags: Matrices

Graph traversal
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)

Starter code:
#User function Template for python3



class Solution():

    def water_flow(self, mat, n, m):

        #your code goes here

        

Solutions:
class Solution:

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

		def dfs(i, j, ref_set, prev):
			if i < 0 or j < 0 or i >= n or (j >= m) or (grid[i][j] < prev) or ((i, j) in ref_set):
				return 0
			ref_set.add((i, j))
			dfs(i + 1, j, ref_set, grid[i][j])
			dfs(i - 1, j, ref_set, grid[i][j])
			dfs(i, j + 1, ref_set, grid[i][j])
			dfs(i, j - 1, ref_set, grid[i][j])
		n = len(grid)
		m = len(grid[0])
		pacific = set()
		atlantic = set()
		for i in range(n):
			dfs(i, 0, pacific, grid[i][0])
			dfs(i, m - 1, atlantic, grid[i][m - 1])
		for i in range(m):
			dfs(0, i, pacific, grid[0][i])
			dfs(n - 1, i, atlantic, grid[n - 1][i])
		common_list = set(pacific).intersection(atlantic)
		return len(common_list)


from collections import deque
from itertools import product
ARABIAN_VISITED = 1
ARABIAN = 2
INDIAN_VISITED = 4
INDIAN = 8

class Solution:

	def _moves_in_range(self, a, n):
		if a > 0:
			yield (a - 1)
		if a < n - 1:
			yield (a + 1)

	def moves(self, x, y, n, m):
		for x1 in self._moves_in_range(x, n):
			yield (x1, y)
		for y1 in self._moves_in_range(y, m):
			yield (x, y1)

	def dfs(self, mat, q, reach, visited_flag, water_flag):
		while q:
			(x, y) = q.pop()
			if reach[x][y] & visited_flag:
				continue
			reach[x][y] |= visited_flag | water_flag
			height = mat[x][y]
			for (x1, y1) in self.moves(x, y, n, m):
				if reach[x1][y1] & visited_flag:
					continue
				if mat[x1][y1] >= height:
					q.append((x1, y1))

	def water_flow(self, mat, n, m):
		indian_q = deque()
		arabian_q = deque()
		reach = [[0] * m for _ in range(n)]
		for i in range(n):
			indian_q.append((i, 0))
			arabian_q.append((i, m - 1))
		for i in range(m):
			indian_q.append((0, i))
			arabian_q.append((n - 1, i))
		self.dfs(mat, arabian_q, reach, ARABIAN_VISITED, ARABIAN)
		self.dfs(mat, indian_q, reach, INDIAN_VISITED, INDIAN)
		both_count = 0
		for x in range(n):
			for y in range(m):
				if reach[x][y] & ARABIAN and reach[x][y] & INDIAN:
					both_count += 1
		return both_count


class Solution:

	def is_flow_ocean(self, mat, ocean, n, m, prev):
		if n < 0 or m < 0 or n >= len(mat) or (m >= len(mat[0])):
			return
		elif ocean[n][m] or mat[n][m] < prev:
			return
		ocean[n][m] = True
		self.is_flow_ocean(mat, ocean, n + 1, m, mat[n][m])
		self.is_flow_ocean(mat, ocean, n - 1, m, mat[n][m])
		self.is_flow_ocean(mat, ocean, n, m + 1, mat[n][m])
		self.is_flow_ocean(mat, ocean, n, m - 1, mat[n][m])

	def water_flow(self, mat, n, m):
		answer = 0
		indian_ocean = [[False] * (m + 1) for _ in range(n + 1)]
		arabic_ocean = [[False] * (m + 1) for _ in range(n + 1)]
		for i in range(n):
			self.is_flow_ocean(mat, indian_ocean, i, 0, mat[i][0])
			self.is_flow_ocean(mat, arabic_ocean, i, m - 1, mat[i][m - 1])
		for j in range(m):
			self.is_flow_ocean(mat, indian_ocean, 0, j, mat[0][j])
			self.is_flow_ocean(mat, arabic_ocean, n - 1, j, mat[n - 1][j])
		for i in range(n):
			for j in range(m):
				if indian_ocean[i][j] and arabic_ocean[i][j]:
					answer += 1
		return answer


class Solution:

	def isValid(self, r, c, n, m):
		if r >= n or r < 0 or c >= m or (c < 0):
			return False
		return True

	def dfs(self, prev, r, c, mat, vis, n, m):
		if not self.isValid(r, c, n, m):
			return
		if vis[r][c]:
			return
		if mat[r][c] < prev:
			return
		vis[r][c] = True
		self.dfs(mat[r][c], r + 1, c, mat, vis, n, m)
		self.dfs(mat[r][c], r - 1, c, mat, vis, n, m)
		self.dfs(mat[r][c], r, c - 1, mat, vis, n, m)
		self.dfs(mat[r][c], r, c + 1, mat, vis, n, m)

	def water_flow(self, mat, n, m):
		indian = [[False for i in range(m)] for i in range(n)]
		arabian = [[False for i in range(m)] for i in range(n)]
		self.dfs(-1, 0, 4, mat, indian, n, m)
		for i in range(n):
			self.dfs(-1, i, 0, mat, indian, n, m)
		for i in range(m):
			self.dfs(-1, 0, i, mat, indian, n, m)
		for i in range(n):
			self.dfs(-1, i, m - 1, mat, arabian, n, m)
		for i in range(m):
			self.dfs(-1, n - 1, i, mat, arabian, n, m)
		ct = 0
		for i in range(n):
			for j in range(m):
				if indian[i][j] and arabian[i][j]:
					ct += 1
		return ct


class Solution:

	def water_flow(self, mat, n, m):
		indian = [[0 for i in range(m)] for j in range(n)]
		arabian = [[0 for i in range(m)] for j in range(n)]
		count = 0

		def condition(i, j, arr, mat, prev):
			if 0 <= i < n and 0 <= j < m and (arr[i][j] != 1) and (mat[i][j] >= prev):
				return True
			else:
				return False

		def dfs(i, j, arr, mat):
			arr[i][j] = 1
			if condition(i - 1, j, arr, mat, mat[i][j]):
				dfs(i - 1, j, arr, mat)
			if condition(i + 1, j, arr, mat, mat[i][j]):
				dfs(i + 1, j, arr, mat)
			if condition(i, j + 1, arr, mat, mat[i][j]):
				dfs(i, j + 1, arr, mat)
			if condition(i, j - 1, arr, mat, mat[i][j]):
				dfs(i, j - 1, arr, mat)
		for j in range(m):
			dfs(0, j, indian, mat)
			dfs(n - 1, j, arabian, mat)
		for i in range(n):
			dfs(i, 0, indian, mat)
			dfs(i, m - 1, arabian, mat)
		for i in range(n):
			for j in range(m):
				if arabian[i][j] == 1 and indian[i][j] == 1:
					count += 1
		return count


from collections import deque

class Solution:

	def bfs(self, mat, n, m, src):
		Q = deque(src)
		visited = set(src)
		while Q:
			(x, y) = Q.popleft()
			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 (mat[nx][ny] >= mat[x][y]) and ((nx, ny) not in visited):
					Q.append((nx, ny))
					visited.add((nx, ny))
		return visited

	def water_flow(self, mat, n, m):
		visited1 = self.bfs(mat, n, m, [(i, 0) for i in range(n)] + [(0, j) for j in range(m)])
		visited2 = self.bfs(mat, n, m, [(i, m - 1) for i in range(n)] + [(n - 1, j) for j in range(m)])
		return len(visited1 & visited2)


class Solution:

	def fill_matrix(self, mat, vis, n, m, row, col):
		if row < 0 or col < 0 or row >= n or (col >= m) or (vis[row][col] == 1):
			return
		vis[row][col] = 1
		if row > 0 and mat[row - 1][col] >= mat[row][col]:
			self.fill_matrix(mat, vis, n, m, row - 1, col)
		if row < n - 1 and mat[row + 1][col] >= mat[row][col]:
			self.fill_matrix(mat, vis, n, m, row + 1, col)
		if col > 0 and mat[row][col - 1] >= mat[row][col]:
			self.fill_matrix(mat, vis, n, m, row, col - 1)
		if col < m - 1 and mat[row][col + 1] >= mat[row][col]:
			self.fill_matrix(mat, vis, n, m, row, col + 1)

	def water_flow(self, mat, n, m):
		indian = [[0 for j in range(m)] for i in range(n)]
		arabian = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			if indian[i][0] == 0:
				self.fill_matrix(mat, indian, n, m, i, 0)
		for j in range(m):
			if indian[0][j] == 0:
				self.fill_matrix(mat, indian, n, m, 0, j)
		for i in range(n):
			if arabian[i][m - 1] == 0:
				self.fill_matrix(mat, arabian, n, m, i, m - 1)
		for j in range(m):
			if arabian[n - 1][j] == 0:
				self.fill_matrix(mat, arabian, n, m, n - 1, j)
		tot_isl = 0
		for i in range(n):
			for j in range(m):
				if indian[i][j] and arabian[i][j]:
					tot_isl += 1
		return tot_isl


from collections import deque

class Solution:

	def water_flow(self, mat, n, m):
		self.count = 0
		directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

		def isValid(x, y):
			return 0 <= x < n and 0 <= y < m

		def dfs(q):
			queue = deque(q)
			seen = set(q)
			while queue:
				(row, col) = queue.popleft()
				for (dx, dy) in directions:
					next_r = row + dy
					next_c = col + dx
					if isValid(next_r, next_c) and mat[next_r][next_c] >= mat[row][col] and ((next_r, next_c) not in seen):
						queue.append((next_r, next_c))
						seen.add((next_r, next_c))
			return seen
		i_cells = [(0, c) for c in range(m)] + [(r, 0) for r in range(n)]
		a_cells = [(n - 1, c) for c in range(m)] + [(r, m - 1) for r in range(n)]
		tot_i = dfs(i_cells)
		tot_a = dfs(a_cells)
		return len(tot_i & tot_a)


class Solution:

	def water_flow(self, mat, n, m):
		n = len(mat)
		m = len(mat[0])
		indian = set()
		arabian = set()

		def dfs(r, c, visit, height):
			if (r, c) in visit or r not in range(n) or c not in range(m) or (mat[r][c] < height):
				return
			visit.add((r, c))
			dfs(r - 1, c, visit, mat[r][c])
			dfs(r, c + 1, visit, mat[r][c])
			dfs(r, c - 1, visit, mat[r][c])
			dfs(r + 1, c, visit, mat[r][c])
		for i in range(m):
			dfs(0, i, indian, mat[0][i])
			dfs(n - 1, i, arabian, mat[n - 1][i])
		for i in range(n):
			dfs(i, 0, indian, mat[i][0])
			dfs(i, m - 1, arabian, mat[i][m - 1])
		out = indian.intersection(arabian)
		return len(out)


class Solution:

	def water_flow(self, mat, n, m):
		dr = [1, -1, 0, 0]
		dc = [0, 0, -1, 1]
		arr = [[0 for i in range(m)] for j in range(n)]

		def bfs(l1, vis):
			l2 = []
			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 < n and (nc >= 0) and (nc < m):
							if mat[nr][nc] >= mat[cr][cc] and (nr, nc) not in vis:
								vis[nr, nc] = 1
								arr[nr][nc] += 1
								l2.append([nr, nc])
				l1 = l2[:]
				l2 = []
		l1 = []
		vis = {}
		for i in range(n):
			l1.append([i, 0])
			vis[i, 0] = 1
			arr[i][0] += 1
		for i in range(1, m):
			l1.append([0, i])
			vis[0, i] = 1
			arr[0][i] += 1
		bfs(l1, vis)
		vis = {}
		l1 = []
		for i in range(n):
			l1.append([i, m - 1])
			vis[i, m - 1] = 1
			arr[i][m - 1] += 1
		for i in range(m - 1):
			l1.append([n - 1, i])
			vis[n - 1, i] = 1
			arr[n - 1][i] += 1
		bfs(l1, vis)
		ans = 0
		for i in range(n):
			for j in range(m):
				if arr[i][j] == 2:
					ans += 1
		return ans


class Solution:

	def water_flow(self, mat, n, m):
		arab = [[0] * m for _ in range(n)]
		stack = []
		for i in range(n):
			stack.append((i, m - 1))
		for j in range(m):
			stack.append((n - 1, j))
		while stack:
			(i, j) = stack.pop()
			arab[i][j] = 1
			if i > 0 and (not arab[i - 1][j]) and (mat[i - 1][j] >= mat[i][j]):
				stack.append((i - 1, j))
			if i < n - 1 and (not arab[i + 1][j]) and (mat[i + 1][j] >= mat[i][j]):
				stack.append((i + 1, j))
			if j > 0 and (not arab[i][j - 1]) and (mat[i][j - 1] >= mat[i][j]):
				stack.append((i, j - 1))
			if j < m - 1 and (not arab[i][j + 1]) and (mat[i][j + 1] >= mat[i][j]):
				stack.append((i, j + 1))
		indi = [[0] * m for _ in range(n)]
		stack = []
		for i in range(n):
			stack.append((i, 0))
		for j in range(m):
			stack.append((0, j))
		while stack:
			(i, j) = stack.pop()
			indi[i][j] = 1
			if i > 0 and (not indi[i - 1][j]) and (mat[i - 1][j] >= mat[i][j]):
				stack.append((i - 1, j))
			if i < n - 1 and (not indi[i + 1][j]) and (mat[i + 1][j] >= mat[i][j]):
				stack.append((i + 1, j))
			if j > 0 and (not indi[i][j - 1]) and (mat[i][j - 1] >= mat[i][j]):
				stack.append((i, j - 1))
			if j < m - 1 and (not indi[i][j + 1]) and (mat[i][j + 1] >= mat[i][j]):
				stack.append((i, j + 1))
		count = 0
		for i in range(n):
			for j in range(m):
				count += arab[i][j] and indi[i][j]
		return count


class Solution:

	def dfs(self, matrix, island, prev, i, j, row, col):
		if i < row and j < col and (i >= 0) and (j >= 0):
			if matrix[i][j]:
				return
			if prev <= island[i][j]:
				matrix[i][j] = 1
				self.dfs(matrix, island, island[i][j], i + 1, j, row, col)
				self.dfs(matrix, island, island[i][j], i - 1, j, row, col)
				self.dfs(matrix, island, island[i][j], i, j + 1, row, col)
				self.dfs(matrix, island, island[i][j], i, j - 1, row, col)

	def water_flow(self, mat, n, m):
		indian = [[0 for x in range(m)] for x in range(n)]
		arabian = [[0 for x in range(m)] for x in range(n)]
		for i in range(0, m):
			self.dfs(indian, mat, mat[0][i], 0, i, n, m)
			self.dfs(arabian, mat, mat[n - 1][i], n - 1, i, n, m)
		for i in range(0, n):
			self.dfs(indian, mat, mat[i][0], i, 0, n, m)
			self.dfs(arabian, mat, mat[i][m - 1], i, m - 1, n, m)
		ans = 0
		for i in range(0, n):
			for j in range(0, m):
				if indian[i][j] == 1 and arabian[i][j] == 1:
					ans += 1
		return ans


from copy import deepcopy

class Solution:

	def answer(self, mat, n, m, i, j, visited, prev):
		if i < 0 or i >= n or j < 0 or (j >= m) or visited[i][j] or (prev > mat[i][j]):
			return
		visited[i][j] = True
		self.answer(mat, n, m, i, j + 1, visited, mat[i][j])
		self.answer(mat, n, m, i, j - 1, visited, mat[i][j])
		self.answer(mat, n, m, i - 1, j, visited, mat[i][j])
		self.answer(mat, n, m, i + 1, j, visited, mat[i][j])

	def answer_util(self, mat, n, m):
		indian_ocean = [[False for col in range(m)] for row in range(n)]
		arabian_sea = [[False for col in range(m)] for row in range(n)]
		for i in range(n):
			self.answer(mat, n, m, i, 0, indian_ocean, mat[i][0])
			self.answer(mat, n, m, i, m - 1, arabian_sea, mat[i][m - 1])
		for j in range(m):
			self.answer(mat, n, m, 0, j, indian_ocean, mat[0][j])
			self.answer(mat, n, m, n - 1, j, arabian_sea, mat[n - 1][j])
		cnt = 0
		for i in range(n):
			for j in range(m):
				if indian_ocean[i][j] & arabian_sea[i][j]:
					cnt += 1
		return cnt

	def columns(self, mat, n, m):
		_left_ = [[False for col in range(m)] for row in range(n)]
		_right_ = [[False for col in range(m)] for row in range(n)]
		_up_ = [[False for col in range(m)] for row in range(n)]
		_down_ = [[False for col in range(m)] for row in range(n)]
		for row in range(n):
			_mx_ = mat[row][0]
			for col in range(m):
				if col == 0:
					_left_[row][col] = True
					continue
				_left_[row][col] = True
				if mat[row][col] < _mx_:
					_left_[row][col] = False
				if _mx_ < mat[row][col]:
					_mx_ = mat[row][col]
		for row in range(n):
			_mx_ = mat[row][m - 1]
			for col in range(m - 1, -1, -1):
				if col == m - 1:
					_right_[row][col] = True
					continue
				if mat[row][col] >= _mx_:
					_right_[row][col] = True
				if _mx_ < mat[row][col]:
					_mx_ = mat[row][col]
		for col in range(m):
			_mx_ = mat[0][col]
			for row in range(n):
				if row == 0:
					_up_[row][col] = True
					continue
				if mat[row][col] >= _mx_:
					_up_[row][col] = True
				if _mx_ < mat[row][col]:
					_mx_ = mat[row][col]
		for col in range(m):
			_mx_ = mat[n - 1][col]
			for row in range(n - 1, -1, -1):
				if row == n - 1:
					_down_[row][col] = True
					continue
				if mat[row][col] >= _mx_:
					_down_[row][col] = True
				if _mx_ < mat[row][col]:
					_mx_ = mat[row][col]
		cnt = 0
		for row in range(n):
			for col in range(m):
				if (_left_[row][col] and _up_[row][col]) and (_right_[row][col] and _down_[row][col]):
					cnt += 1
		return cnt

	def water_flow(self, mat, n, m):
		cnt = self.answer_util(mat, n, m)
		return cnt


class Solution:

	def water_flow(self, mat, rows, cols):
		indian = self.bfs(mat, rows, cols, [(0, i) for i in range(cols)] + [(j, 0) for j in range(rows)])
		arabic = self.bfs(mat, rows, cols, [(i, cols - 1) for i in range(rows)] + [(rows - 1, j) for j in range(cols)])
		return len(indian & arabic)

	def bfs(self, mat, rows, cols, edges):
		visited = set(edges)
		stack = edges
		while stack:
			(x, y) = stack.pop(0)
			for (nx, ny) in [[x, y + 1], [x, y - 1], [x + 1, y], [x - 1, y]]:
				if 0 <= nx < rows and 0 <= ny < cols and (mat[nx][ny] >= mat[x][y]) and ((nx, ny) not in visited):
					stack.append((nx, ny))
					visited.add((nx, ny))
		return visited


from collections import deque

class Solution:

	def BFS(self, mat, i, j, visited):
		q = deque()
		q.append((i, j))
		visited[i][j] = True
		while q:
			(i, j) = q.popleft()
			if i + 1 <= n - 1 and mat[i][j] <= mat[i + 1][j] and (not visited[i + 1][j]):
				q.append((i + 1, j))
				visited[i + 1][j] = True
			if j + 1 <= m - 1 and mat[i][j] <= mat[i][j + 1] and (not visited[i][j + 1]):
				q.append((i, j + 1))
				visited[i][j + 1] = True
			if i - 1 >= 0 and mat[i][j] <= mat[i - 1][j] and (not visited[i - 1][j]):
				q.append((i - 1, j))
				visited[i - 1][j] = True
			if j - 1 >= 0 and mat[i][j] <= mat[i][j - 1] and (not visited[i][j - 1]):
				q.append((i, j - 1))
				visited[i][j - 1] = True

	def water_flow(self, mat, n, m):
		visited_indian = [[False for i in range(m)] for j in range(n)]
		visited_arabian = [[False for i in range(m)] for j in range(n)]
		for j in range(m):
			if not visited_indian[0][j]:
				self.BFS(mat, 0, j, visited_indian)
		for i in range(n):
			if not visited_indian[i][0]:
				self.BFS(mat, i, 0, visited_indian)
		for j in range(m):
			if not visited_arabian[n - 1][j]:
				self.BFS(mat, n - 1, j, visited_arabian)
		for i in range(n):
			if not visited_arabian[i][m - 1]:
				self.BFS(mat, i, m - 1, visited_arabian)
		cnt = 0
		for i in range(n):
			for j in range(m):
				if visited_indian[i][j] == True and visited_arabian[i][j] == True:
					cnt += 1
		return cnt


class Solution:

	def water_flow(self, mat, n, m):
		indian = [[0 for i in range(m)] for i in range(n)]
		arabian = [[0 for i in range(m)] for i in range(n)]
		visited = [[0 for i in range(m)] for i in range(n)]
		visited1 = [[0 for i in range(m)] for i in range(n)]

		def f(i, j):
			visited[i][j] = 1
			indian[i][j] = 1
			for (ii, jj) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
				if 0 <= i - ii < n and 0 <= j - jj < m and (not visited[i - ii][j - jj]) and (mat[i][j] <= mat[i - ii][j - jj]):
					f(i - ii, j - jj)
		for i in range(m):
			if visited[0][i]:
				continue
			else:
				f(0, i)
		for i in range(n):
			if visited[i][0]:
				continue
			else:
				f(i, 0)

		def ff(i, j):
			visited1[i][j] = 1
			arabian[i][j] = 1
			for (ii, jj) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
				if 0 <= i - ii < n and 0 <= j - jj < m and (not visited1[i - ii][j - jj]) and (mat[i][j] <= mat[i - ii][j - jj]):
					ff(i - ii, j - jj)
		for i in range(m):
			if visited1[n - 1][i]:
				continue
			else:
				ff(n - 1, i)
		for i in range(n):
			if visited1[i][m - 1]:
				continue
			else:
				ff(i, m - 1)
		ans = 0
		for i in range(n):
			for j in range(m):
				if arabian[i][j] and indian[i][j]:
					ans += 1
		return ans


from collections import deque

class Solution:

	def check(self, mat, n, m, indices, dic):
		q = deque(indices)
		visited = set(indices)
		while q:
			(x, y) = q.popleft()
			for (i, j) in dic:
				i += x
				j += y
				if 0 <= i < n and 0 <= j < m and (mat[i][j] >= mat[x][y]) and ((i, j) not in visited):
					visited.add((i, j))
					q.append((i, j))
		return visited

	def water_flow(self, mat, n, m):
		dic = {(0, 1), (0, -1), (1, 0), (-1, 0)}
		v1 = self.check(mat, n, m, [(0, i) for i in range(m)] + [(j, 0) for j in range(n)], dic)
		v2 = self.check(mat, n, m, [(n - 1, i) for i in range(m)] + [(j, m - 1) for j in range(n)], dic)
		v1 = v1.intersection(v2)
		return len(v1)


class Solution:

	def dfs(self, i, j, pari, parj, mat, ab, a, b):
		if i - 1 >= 0:
			if i - 1 != pari or j != parj:
				if mat[i - 1][j] >= mat[i][j]:
					if ab == 0:
						if a[i - 1][j] == 0:
							a[i - 1][j] = 1
							self.dfs(i - 1, j, i, j, mat, 0, a, b)
					elif ab == 1:
						if b[i - 1][j] == 0:
							b[i - 1][j] = 1
							self.dfs(i - 1, j, i, j, mat, 1, a, b)
		if j - 1 >= 0:
			if i != pari or j - 1 != parj:
				if mat[i][j - 1] >= mat[i][j]:
					if ab == 0:
						if a[i][j - 1] == 0:
							a[i][j - 1] = 1
							self.dfs(i, j - 1, i, j, mat, 0, a, b)
					elif ab == 1:
						if b[i][j - 1] == 0:
							b[i][j - 1] = 1
							self.dfs(i, j - 1, i, j, mat, 1, a, b)
		if i + 1 < n:
			if i + 1 != pari or j != parj:
				if mat[i + 1][j] >= mat[i][j]:
					if ab == 0:
						if a[i + 1][j] == 0:
							a[i + 1][j] = 1
							self.dfs(i + 1, j, i, j, mat, 0, a, b)
					elif ab == 1:
						if b[i + 1][j] == 0:
							b[i + 1][j] = 1
							self.dfs(i + 1, j, i, j, mat, 1, a, b)
		if j + 1 < m:
			if i != pari or j + 1 != parj:
				if mat[i][j + 1] >= mat[i][j]:
					if ab == 0:
						if a[i][j + 1] == 0:
							a[i][j + 1] = 1
							self.dfs(i, j + 1, i, j, mat, 0, a, b)
					elif ab == 1:
						if b[i][j + 1] == 0:
							b[i][j + 1] = 1
							self.dfs(i, j + 1, i, j, mat, 1, a, b)

	def water_flow(self, mat, n, m):
		a = [[0 for i in range(m)] for j in range(n)]
		b = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			a[i][0] = 1
		for j in range(m):
			a[0][j] = 1
		for i in range(n):
			b[i][m - 1] = 1
		for j in range(m):
			b[n - 1][j] = 1
		for i in range(n):
			self.dfs(i, 0, -1, -1, mat, 0, a, b)
		for j in range(m):
			self.dfs(0, j, -1, -1, mat, 0, a, b)
		for i in range(n):
			self.dfs(i, m - 1, -1, -1, mat, 1, a, b)
		for j in range(m):
			self.dfs(n - 1, j, -1, -1, mat, 1, a, b)
		count = 0
		for i in range(n):
			for j in range(m):
				if a[i][j] == 1 and b[i][j] == 1:
					count += 1
		return count


def dfs(mat, visited, i, j, height):
	if i < 0 or i >= len(mat) or j < 0 or (j >= len(mat[0])):
		return
	if mat[i][j] < height or visited[i][j]:
		return
	visited[i][j] = True
	dfs(mat, visited, i + 1, j, mat[i][j])
	dfs(mat, visited, i - 1, j, mat[i][j])
	dfs(mat, visited, i, j + 1, mat[i][j])
	dfs(mat, visited, i, j - 1, mat[i][j])

class Solution:

	def water_flow(self, mat, n, m):
		rows = n
		cols = m
		visited_from_ocean = [[False] * cols for _ in range(rows)]
		visited_from_sea = [[False] * cols for _ in range(rows)]
		for j in range(cols):
			dfs(mat, visited_from_ocean, 0, j, mat[0][j])
		for j in range(cols):
			dfs(mat, visited_from_sea, rows - 1, j, mat[rows - 1][j])
		for i in range(rows):
			dfs(mat, visited_from_ocean, i, 0, mat[i][0])
		for i in range(rows):
			dfs(mat, visited_from_sea, i, cols - 1, mat[i][cols - 1])
		count = 0
		for i in range(rows):
			for j in range(cols):
				if visited_from_ocean[i][j] and visited_from_sea[i][j]:
					count += 1
		return count


class Solution:

	def water_flow(self, mat, n, m):
		self.n = n
		self.m = m
		indianOcean = [[False] * m for _ in range(n)]
		pacificOcean = [[False] * m for _ in range(n)]
		for i in range(n):
			self.fill_water(i, 0, -1, mat, indianOcean)
			self.fill_water(i, m - 1, -1, mat, pacificOcean)
		for j in range(m):
			self.fill_water(0, j, -1, mat, indianOcean)
			self.fill_water(n - 1, j, -1, mat, pacificOcean)
		result = 0
		for i in range(n):
			for j in range(m):
				if indianOcean[i][j] and pacificOcean[i][j]:
					result += 1
		return result

	def fill_water(self, i, j, prev, mat, ocean):
		if not (0 <= i < self.n and 0 <= j < self.m and (not ocean[i][j])):
			return
		if prev > mat[i][j]:
			return
		ocean[i][j] = True
		self.fill_water(i + 1, j, mat[i][j], mat, ocean)
		self.fill_water(i, j + 1, mat[i][j], mat, ocean)
		self.fill_water(i - 1, j, mat[i][j], mat, ocean)
		self.fill_water(i, j - 1, mat[i][j], mat, ocean)


class Solution:

	def water_flow(self, mat, n, m):
		moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
		check = lambda x, y: 0 <= x < n and 0 <= y < m

		def recur(x, y, visited):
			visited[x][y] = True
			for (dx, dy) in moves:
				if check(x + dx, y + dy) and (not visited[x + dx][y + dy]) and (mat[x + dx][y + dy] >= mat[x][y]):
					recur(x + dx, y + dy, visited)
		indian = [[False] * m for i in range(n)]
		arabian = [[False] * m for i in range(n)]
		for i in range(m):
			recur(0, i, indian)
			recur(n - 1, i, arabian)
		for i in range(n):
			recur(i, 0, indian)
			recur(i, m - 1, arabian)
		res = 0
		for i in range(n):
			for j in range(m):
				if indian[i][j] and arabian[i][j]:
					res += 1
		return res


class Solution:

	def water_flow(self, mat, n, m):
		ind = [[0 for j in range(m)] for i in range(n)]
		arb = [[0 for j in range(m)] for i in range(n)]

		def fun(i, j, vis):
			if j < 0 or i < 0 or j >= m or (i >= n) or (vis[i][j] == 1):
				return
			vis[i][j] = 1
			if i - 1 >= 0 and vis[i - 1][j] == 0 and (mat[i][j] <= mat[i - 1][j]):
				fun(i - 1, j, vis)
			if j - 1 >= 0 and vis[i][j - 1] == 0 and (mat[i][j] <= mat[i][j - 1]):
				fun(i, j - 1, vis)
			if i + 1 < n and vis[i + 1][j] == 0 and (mat[i][j] <= mat[i + 1][j]):
				fun(i + 1, j, vis)
			if j + 1 < m and vis[i][j + 1] == 0 and (mat[i][j] <= mat[i][j + 1]):
				fun(i, j + 1, vis)
		c = 0
		for j in range(m):
			fun(0, j, ind)
		for i in range(n):
			fun(i, 0, ind)
		for i in range(n):
			fun(i, m - 1, arb)
		for j in range(m):
			fun(n - 1, j, arb)
		for i in range(n):
			for j in range(m):
				if ind[i][j] and arb[i][j]:
					c += 1
		return c


class Solution:

	def water_flow(self, mat, n, m):
		(ind, arb) = (set(), set())

		def dfs(r, c, visit, prev):
			if (r, c) in visit or r < 0 or c < 0 or (r == n) or (c == m) or (mat[r][c] < prev):
				return
			visit.add((r, c))
			dfs(r + 1, c, visit, mat[r][c])
			dfs(r - 1, c, visit, mat[r][c])
			dfs(r, c + 1, visit, mat[r][c])
			dfs(r, c - 1, visit, mat[r][c])
		for c in range(m):
			dfs(0, c, ind, mat[0][c])
			dfs(n - 1, c, arb, mat[n - 1][c])
		for r in range(n):
			dfs(r, 0, ind, mat[r][0])
			dfs(r, m - 1, arb, mat[r][m - 1])
		cnt = 0
		for r in range(n):
			for c in range(m):
				if (r, c) in ind and (r, c) in arb:
					cnt += 1
		return cnt


class Solution:

	def water_flow(self, mat, n, m):

		def valid(i, j, n, m, vis, p, mat):
			if i >= 0 and j >= 0 and (i < n) and (j < m) and (vis[i][j] != True) and (p <= mat[i][j]):
				return True
			return False
		vis = [[False for i in range(m)] for j in range(n)]
		q = []
		for i in range(m):
			vis[0][i] = True
			q.append([0, i])
		for i in range(1, n):
			vis[i][0] = True
			q.append([i, 0])
		indian = dict()
		while q:
			(i, j) = q.pop(0)
			vis[i][j] = True
			if (i, j) not in indian:
				indian[i, j] = True
			if valid(i + 1, j, n, m, vis, mat[i][j], mat):
				vis[i + 1][j] = True
				q.append([i + 1, j])
			if valid(i, j + 1, n, m, vis, mat[i][j], mat):
				vis[i][j + 1] = True
				q.append([i, j + 1])
			if valid(i - 1, j, n, m, vis, mat[i][j], mat):
				vis[i - 1][j] = True
				q.append([i - 1, j])
			if valid(i, j - 1, n, m, vis, mat[i][j], mat):
				vis[i][j - 1] = True
				q.append([i, j - 1])
		vi = [[False for i in range(m)] for j in range(n)]
		for i in range(n):
			q.append([i, m - 1])
			vi[i][m - 1] = True
		for j in range(m - 1):
			q.append([n - 1, j])
			vi[n - 1][j] = True
		c = 0
		while q:
			(i, j) = q.pop(0)
			vi[i][j] = True
			if (i, j) in indian and indian[i, j] == True:
				c += 1
			if valid(i + 1, j, n, m, vi, mat[i][j], mat):
				vi[i + 1][j] = True
				q.append([i + 1, j])
			if valid(i, j + 1, n, m, vi, mat[i][j], mat):
				vi[i][j + 1] = True
				q.append([i, j + 1])
			if valid(i - 1, j, n, m, vi, mat[i][j], mat):
				vi[i - 1][j] = True
				q.append([i - 1, j])
			if valid(i, j - 1, n, m, vi, mat[i][j], mat):
				vi[i][j - 1] = True
				q.append([i, j - 1])
		return c


import sys
sys.setrecursionlimit(1000000)
ct = 0

def dfs(a, i, j, visited):
	if (i, j) in visited:
		return
	visited.add((i, j))
	if i > 0 and a[i][j] <= a[i - 1][j]:
		dfs(a, i - 1, j, visited)
	if j > 0 and a[i][j] <= a[i][j - 1]:
		dfs(a, i, j - 1, visited)
	if i < len(a) - 1 and a[i][j] <= a[i + 1][j]:
		dfs(a, i + 1, j, visited)
	if j < len(a[0]) - 1 and a[i][j] <= a[i][j + 1]:
		dfs(a, i, j + 1, visited)

class Solution:

	def water_flow(self, mat, n, m):
		ans = 0
		visited = set()
		for i in range(n):
			if (i, 0) not in visited:
				dfs(mat, i, 0, visited)
		for j in range(m):
			if (0, j) not in visited:
				dfs(mat, 0, j, visited)
		s1 = visited.copy()
		visited = set()
		for i in range(n):
			if (i, m - 1) not in visited:
				dfs(mat, i, m - 1, visited)
		for j in range(m):
			if (n - 1, j) not in visited:
				dfs(mat, n - 1, j, visited)
		return len(s1.intersection(visited))


from collections import deque

class Solution:

	def b(self, mat, n, m, s):
		q = deque(s)
		vis = set(s)
		while q:
			(x, y) = q.popleft()
			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 (mat[nx][ny] >= mat[x][y]) and ((nx, ny) not in vis):
					q.append((nx, ny))
					vis.add((nx, ny))
		return vis

	def water_flow(self, mat, n, m):
		v1 = self.b(mat, n, m, [(i, 0) for i in range(n)] + [(0, j) for j in range(m)])
		v2 = self.b(mat, n, m, [(i, m - 1) for i in range(n)] + [(n - 1, j) for j in range(m)])
		return len(v1 & v2)


from collections import deque

class Solution:

	def solve(self, mat, n, m, source):
		q = deque(source)
		seen = set(source)
		while q:
			(x, y) = q.popleft()
			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 (mat[nx][ny] >= mat[x][y]) and ((nx, ny) not in seen):
					q.append((nx, ny))
					seen.add((nx, ny))
		return seen

	def water_flow(self, mat, n, m):
		seen1 = self.solve(mat, n, m, [(i, 0) for i in range(n)] + [(0, j) for j in range(m)])
		seen2 = self.solve(mat, n, m, [(i, m - 1) for i in range(n)] + [(n - 1, j) for j in range(m)])
		return len(seen1 & seen2)


class Solution:

	def water_flow(self, mat, n, m):

		def dfs(i, j, visited):
			visited[i][j] = 1
			if j - 1 >= 0 and visited[i][j - 1] == 0 and (mat[i][j] <= mat[i][j - 1]):
				dfs(i, j - 1, visited)
			if i - 1 >= 0 and visited[i - 1][j] == 0 and (mat[i][j] <= mat[i - 1][j]):
				dfs(i - 1, j, visited)
			if j + 1 < m and visited[i][j + 1] == 0 and (mat[i][j] <= mat[i][j + 1]):
				dfs(i, j + 1, visited)
			if i + 1 < n and visited[i + 1][j] == 0 and (mat[i][j] <= mat[i + 1][j]):
				dfs(i + 1, j, visited)
		ans = 0
		Indian = [[0] * m for _ in range(n)]
		Arabian = [[0] * m for _ in range(n)]
		for i in range(n):
			dfs(i, 0, Indian)
			dfs(i, m - 1, Arabian)
		for i in range(m):
			dfs(0, i, Indian)
			dfs(n - 1, i, Arabian)
		for i in range(n):
			for j in range(m):
				if Indian[i][j] == 1 and Arabian[i][j] == 1:
					ans += 1
		return ans


class Solution:

	def water_flow(self, mat, n, m):
		indian = [[False for i in range(m)] for i in range(n)]
		for i in range(n):
			self.dfs(mat, i, 0, -1, n, m, indian)
		for i in range(m):
			self.dfs(mat, 0, i, -1, n, m, indian)
		arabian = [[False for i in range(m)] for i in range(n)]
		for i in range(n):
			self.dfs(mat, i, m - 1, -1, n, m, arabian)
		for i in range(m):
			self.dfs(mat, n - 1, i, -1, n, m, arabian)
		cnt = 0
		for i in range(n):
			for j in range(m):
				if indian[i][j] and arabian[i][j]:
					cnt += 1
		return cnt

	def dfs(self, mat, i, j, prev, n, m, canTravel):
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		if i < 0 or j < 0 or i >= n or (j >= m) or canTravel[i][j] or (mat[i][j] < prev):
			return
		canTravel[i][j] = True
		for k in range(4):
			self.dfs(mat, i + dx[k], j + dy[k], mat[i][j], n, m, canTravel)