In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the conditions:

Every time you are located in a cell you will collect all the gold in that cell.
From your position you can walk one step to the left, right, up or down.
You can't visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.

 
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

 
Constraints:

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Data structures

Complete search

Starter code: class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		height = len(grid)
		width = len(grid[0])
		max_path = 0

		def index_gen(index):
			(i, j) = index
			if i > 0 and grid[i - 1][j] > 0:
				yield (i - 1, j)
			if i < height - 1 and grid[i + 1][j] > 0:
				yield (i + 1, j)
			if j > 0 and grid[i][j - 1] > 0:
				yield (i, j - 1)
			if j < width - 1 and grid[i][j + 1] > 0:
				yield (i, j + 1)

		def is_viable(index):
			non_zero = 0
			neighbors = [grid[a][b] for (a, b) in index_gen(index)]
			for x in neighbors:
				if x != 0:
					non_zero += 1
			return non_zero < 2

		def dfs(index, count):
			nonlocal max_path
			count += grid[index[0]][index[1]]
			max_path = max(max_path, count)
			grid[index[0]][index[1]] *= -1
			for direction in index_gen(index):
				dfs(direction, count)
			grid[index[0]][index[1]] *= -1
		for i in range(height):
			for j in range(width):
				if grid[i][j] != 0 and is_viable((i, j)):
					dfs((i, j), 0)
		return max_path if max_path > 0 else sum((sum(row) for row in grid))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		a = len(grid)
		b = len(grid[0])
		gold = 0
		visited = [[False for y in range(b)] for x in range(a)]

		def maxgoldpath(x, y, visited):
			if x < 0 or x >= a or y < 0 or (y >= b) or (grid[x][y] == 0) or visited[x][y]:
				return 0
			else:
				visited[x][y] = True
				left = maxgoldpath(x, y - 1, visited)
				right = maxgoldpath(x, y + 1, visited)
				top = maxgoldpath(x - 1, y, visited)
				down = maxgoldpath(x + 1, y, visited)
				visited[x][y] = False
				return max(left + grid[x][y], right + grid[x][y], top + grid[x][y], down + grid[x][y])
		for x in range(a):
			for y in range(b):
				if grid[x][y] > 0:
					gold = max(gold, maxgoldpath(x, y, visited))
		return gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.rLen = len(grid)
		self.cLen = len(grid[0])
		res = 0
		path = None
		for i in range(self.rLen):
			for j in range(self.cLen):
				if grid[i][j] != 0:
					(ret, retPath) = self.dfs(grid, i, j)
					if ret > res:
						res = ret
						path = retPath
		return res

	def dfs(self, grid, i, j):
		if grid[i][j] != 0:
			tmp = grid[i][j]
			grid[i][j] = 0
			maxTotal = 0
			maxPath = []
			for (newI, newJ) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
				if 0 <= newI < len(grid) and 0 <= newJ < len(grid[0]) and (grid[newI][newJ] != 0):
					(retTotal, retPath) = self.dfs(grid, newI, newJ)
					if retTotal > maxTotal:
						maxTotal = retTotal
						maxPath = retPath
			grid[i][j] = tmp
			return (maxTotal + tmp, maxPath + [(i, j)])
		else:
			return (0, [])


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.ans = 0

		def dfs(x, y, curr):
			curr += grid[x][y]
			self.ans = max(curr, self.ans)
			(temp, grid[x][y]) = (grid[x][y], 0)
			for (nx, ny) in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
				if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and (grid[nx][ny] != 0):
					dfs(nx, ny, curr)
			grid[x][y] = temp
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					dfs(i, j, 0)
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i, j, v):
			seen.add((i, j))
			dp[i][j] = max(dp[i][j], v)
			for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= x < m and 0 <= y < n and grid[x][y] and ((x, y) not in seen):
					dfs(x, y, v + grid[x][y])
			seen.discard((i, j))
		(m, n) = (len(grid), len(grid[0]))
		dp = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					seen = set()
					dfs(i, j, grid[i][j])
		return max((c for row in dp for c in row))


class Solution:
	allGod = -1

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def helper(maxgold, i, j):
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] > 0):
				temp = grid[i][j]
				self.allGod = max(self.allGod, maxgold + temp)
				grid[i][j] = 0
				helper(maxgold + temp, i - 1, j)
				helper(maxgold + temp, i + 1, j)
				helper(maxgold + temp, i, j - 1)
				helper(maxgold + temp, i, j + 1)
				grid[i][j] = temp
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					helper(0, i, j)
		return self.allGod


class Solution:
	gold = 0

	def dfs(self, grid, i, j, current):
		if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == 0):
			return
		current += grid[i][j]
		temp = grid[i][j]
		grid[i][j] = 0
		self.dfs(grid, i, j - 1, current)
		self.dfs(grid, i, j + 1, current)
		self.dfs(grid, i + 1, j, current)
		self.dfs(grid, i - 1, j, current)
		grid[i][j] = temp
		self.gold = max(self.gold, current)

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					current = 0
					self.dfs(grid, i, j, current)
		return self.gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(row, col, visited, acc=0):
			if (row, col) in visited:
				return 0
			if row < 0 or col < 0 or row >= len(grid) or (col >= len(grid[row])):
				return 0
			if grid[row][col] == 0:
				return 0
			acc += grid[row][col]
			visited.add((row, col))
			ret = max(acc, dfs(row + 1, col, visited, acc), dfs(row - 1, col, visited, acc), dfs(row, col + 1, visited, acc), dfs(row, col - 1, visited, acc))
			visited.remove((row, col))
			return ret
		ret = 0
		for row in range(len(grid)):
			for col in range(len(grid[row])):
				ret = max(ret, dfs(row, col, set()))
		return ret


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.best = 0

		def rec(x, y, total):
			if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (grid[x][y] > 0):
				total += grid[x][y]
				self.best = max(self.best, total)
				grid[x][y] = -grid[x][y]
				rec(x - 1, y, total)
				rec(x, y - 1, total)
				rec(x + 1, y, total)
				rec(x, y + 1, total)
				grid[x][y] = abs(grid[x][y])
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] != 0:
					rec(r, c, 0)
		return self.best


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def helper(i, j, a):
			if i in [-1, len(grid)] or j in [-1, len(grid[0])] or grid[i][j] in [-1, 0]:
				return a
			y = grid[i][j]
			x = a + y
			grid[i][j] = -1
			a = max(helper(i + 1, j, x), helper(i - 1, j, x), helper(i, j + 1, x), helper(i, j - 1, x))
			grid[i][j] = y
			return a
		ans = -1
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				ans = max(ans, helper(i, j, 0))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		maxCount = 0
		N = len(grid)
		M = len(list(zip(*grid)))
		for row in range(N):
			for col in range(M):
				if grid[row][col] != 0:
					maxCount = max(self.backtrack(grid, row, col, N, M), maxCount)
		return maxCount

	def backtrack(self, grid, row, col, N, M):
		value = grid[row][col]
		grid[row][col] = -1
		maxCollected = 0
		if row + 1 < N and grid[row + 1][col] not in (0, -1):
			maxCollected = max(self.backtrack(grid, row + 1, col, N, M), maxCollected)
		if col + 1 < M and grid[row][col + 1] not in (0, -1):
			maxCollected = max(self.backtrack(grid, row, col + 1, N, M), maxCollected)
		if row - 1 >= 0 and grid[row - 1][col] not in (0, -1):
			maxCollected = max(self.backtrack(grid, row - 1, col, N, M), maxCollected)
		if col - 1 >= 0 and grid[row][col - 1] not in (0, -1):
			maxCollected = max(self.backtrack(grid, row, col - 1, N, M), maxCollected)
		grid[row][col] = value
		return value + maxCollected


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i: int, j: int, sum: int, seen: set) -> int:
			mx = sum
			for (x, y) in ((i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)):
				if not (x < 0 or x >= m or y < 0 or (y >= n) or (not grid[x][y]) or ((x, y) in seen)):
					mx = max(dfs(x, y, sum + grid[x][y], seen | {(x, y)}), mx)
			return mx
		(m, n) = (len(grid), len(grid[0]))
		res = 0
		for j in range(n):
			for i in range(m):
				if grid[i][j] != 0:
					seen = set()
					seen.add((i, j))
					sum = grid[i][j]
					res = max(res, dfs(i, j, sum, seen))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		res = 0

		def dfs(x, y, grid):
			if x < 0 or x > len(grid) - 1 or y < 0 or (y > len(grid[0]) - 1) or (grid[x][y] == 0):
				return 0
			temp = grid[x][y]
			grid[x][y] = 0
			a = dfs(x + 1, y, grid) + temp
			b = dfs(x, y + 1, grid) + temp
			c = dfs(x - 1, y, grid) + temp
			d = dfs(x, y - 1, grid) + temp
			res = max([a, b, c, d])
			grid[x][y] = temp
			return res
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					res = max(dfs(i, j, grid), res)
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def collect(row, col, visited, curr_sum, ans):
			if row >= 0 and col >= 0 and (row < len(grid)) and (col < len(grid[0])) and (visited[row][col] == False) and (grid[row][col] != 0):
				curr_sum += grid[row][col]
				ans[0] = max(ans[0], curr_sum)
				visited[row][col] = True
				collect(row + 1, col, visited, curr_sum, ans)
				collect(row - 1, col, visited, curr_sum, ans)
				collect(row, col + 1, visited, curr_sum, ans)
				collect(row, col - 1, visited, curr_sum, ans)
				visited[row][col] = False
		visited = [[False for i in range(len(grid[0]))] for j in range(len(grid))]
		ans = [0]
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if grid[row][col] != 0:
					collect(row, col, visited, 0, ans)
		return ans[0]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.res = 0
		direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

		def dfs(i, j, cur):
			cur += grid[i][j]
			end = True
			for (di, dj) in direction:
				(i1, j1) = (i + di, j + dj)
				if 0 <= i1 < len(grid) and 0 <= j1 < len(grid[0]) and (grid[i1][j1] > 0) and ((i1, j1) not in visited):
					visited.add((i1, j1))
					dfs(i1, j1, cur)
					visited.discard((i1, j1))
					end = False
			if end:
				self.res = max(self.res, cur)
			return
		(m, n) = (len(grid), len(grid[0]))
		for i in range(m):
			for j in range(n):
				if grid[i][j] > 0:
					visited = set([(i, j)])
					dfs(i, j, 0)
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i, j, seen):
			if i < 0 or j < 0 or j >= len(grid[0]) or (i >= len(grid)) or ((i, j) in seen) or (grid[i][j] == 0):
				return 0
			seen.add((i, j))
			t = grid[i][j] + max(dfs(i + 1, j, seen), dfs(i, j + 1, seen), dfs(i - 1, j, seen), dfs(i, j - 1, seen))
			seen.remove((i, j))
			return t
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				ans = max(dfs(i, j, set()), ans)
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		l = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		vis = set()
		res = [0]
		z = -float('inf')

		def fn(a, b):
			z = -float('inf')
			for (c, d) in l:
				(x, y) = (a + c, b + d)
				if x < 0 or x >= m or y < 0 or (y >= n):
					continue
				if (x, y) not in vis and grid[x][y] > 0:
					vis.add((x, y))
					res[0] += grid[x][y]
					z = max(z, fn(x, y))
					res[0] -= grid[x][y]
					vis.remove((x, y))
			if z == -float('inf'):
				return res[0]
			return z
		for x in range(m):
			for y in range(n):
				if grid[x][y] > 0:
					vis.add((x, y))
					res[0] += grid[x][y]
					z = max(z, fn(x, y))
					res[0] -= grid[x][y]
					vis.remove((x, y))
		if z == -float('inf'):
			return 0
		return z


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		self.answer = 0

		def dfs(i, j):
			if i < 0 or i >= len(grid):
				return 0
			if j < 0 or j >= len(grid[0]):
				return 0
			if grid[i][j] == 0:
				return 0
			temp = grid[i][j]
			grid[i][j] = 0
			storage = temp + max(dfs(i + 1, j), dfs(i - 1, j), dfs(i, j - 1), dfs(i, j + 1))
			self.answer = max(self.answer, storage)
			grid[i][j] = temp
			return storage
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				dfs(i, j)
		return self.answer


from typing import List

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		rows = len(grid)
		if not rows:
			return 0
		cols = len(grid[0])

		def dfs(i, j):
			if i < 0 or j < 0 or i >= rows or (j >= cols) or (grid[i][j] == 0):
				return 0
			val = grid[i][j]
			_sum = val
			grid[i][j] = 0
			_sum = max(_sum, val + dfs(i - 1, j))
			_sum = max(_sum, val + dfs(i, j - 1))
			_sum = max(_sum, val + dfs(i + 1, j))
			_sum = max(_sum, val + dfs(i, j + 1))
			grid[i][j] = val
			return _sum
		ans = 0
		for i in range(rows):
			for j in range(cols):
				ans = max(ans, dfs(i, j))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dsf(r, c, gold):
			if not (0 <= r < len(grid) and 0 <= c < len(grid[0]) and (grid[r][c] > 0)):
				return
			gold += grid[r][c]
			self.max_gold = max(self.max_gold, gold)
			grid[r][c] *= -1
			dsf(r + 1, c, gold)
			dsf(r - 1, c, gold)
			dsf(r, c + 1, gold)
			dsf(r, c - 1, gold)
			grid[r][c] *= -1
		self.max_gold = 0
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] > 0:
					dsf(r, c, 0)
		return self.max_gold


class Solution:
	max_gold = 0

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(nRow, nCol) = (len(grid), len(grid[0]))
		self.max_gold = max([x for r in grid for x in r])
		path = []

		def helper(kr, kc):
			up = kr == 0 or grid[kr - 1][kc] == 0
			down = kr == nRow - 1 or grid[kr + 1][kc] == 0
			left = kc == 0 or grid[kr][kc - 1] == 0
			right = kc == nCol - 1 or grid[kr][kc + 1] == 0
			if up and down and left and right:
				self.max_gold = max(self.max_gold, sum(path) + grid[kr][kc])
			else:
				path.append(grid[kr][kc])
				grid[kr][kc] = 0
				if not up:
					helper(kr - 1, kc)
				if not down:
					helper(kr + 1, kc)
				if not left:
					helper(kr, kc - 1)
				if not right:
					helper(kr, kc + 1)
				grid[kr][kc] = path.pop()
		for kr in range(nRow):
			for kc in range(nCol):
				if grid[kr][kc]:
					helper(kr, kc)
		return self.max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
		(m, n) = (len(grid), len(grid[0]))

		def dfs(x, y, gold):
			temp = grid[x][y]
			grid[x][y] = 0
			self.max_gold = max(self.max_gold, gold + temp)
			for (dx, dy) in dirs:
				nx = dx + x
				ny = dy + y
				if 0 <= nx < m and 0 <= ny < n and grid[nx][ny]:
					dfs(nx, ny, gold + temp)
			grid[x][y] = temp
		self.max_gold = 0
		for i in range(m):
			for j in range(n):
				dfs(i, j, 0)
		return self.max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i, j, cur):
			nonlocal mx
			cur += grid[i][j]
			mx = max(mx, cur)
			path.add((i, j))
			for (I, J) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= I < len(grid) and 0 <= J < len(grid[0]) and (grid[I][J] != 0) and ((I, J) not in path):
					dfs(I, J, cur)
			path.remove((i, j))
		if not grid:
			return 0
		mx = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					path = set()
					dfs(i, j, 0)
		return mx


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		(n, m) = (len(grid), len(grid[0]))
		dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		self.max_gold = 0
		self.v = set()

		def dfs(r, c, gold):
			self.max_gold = max(self.max_gold, gold)
			for d in dirs:
				(row, col) = (r + d[0], c + d[1])
				if 0 <= row < n and 0 <= col < m and (grid[row][col] != 0) and ((row, col) not in self.v):
					self.v.add((row, col))
					dfs(row, col, gold + grid[row][col])
					self.v.remove((row, col))
		for i in range(n):
			for j in range(m):
				if grid[i][j] != 0:
					self.v.add((i, j))
					dfs(i, j, grid[i][j])
					self.v.remove((i, j))
		return self.max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(row, col, cur_sum, visited):
			if row < 0 or col < 0 or row >= len(grid) or (col >= len(grid[0])) or (visited[row][col] == 1) or (grid[row][col] == 0):
				return
			visited[row][col] = 1
			cur_sum += grid[row][col]
			self.max_path = max(self.max_path, cur_sum)
			dfs(row + 1, col, cur_sum, visited)
			dfs(row - 1, col, cur_sum, visited)
			dfs(row, col + 1, cur_sum, visited)
			dfs(row, col - 1, cur_sum, visited)
			visited[row][col] = 0
		visited = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
		self.max_path = 0
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if grid[row][col] != 0:
					dfs(row, col, 0, visited)
		return self.max_path


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		totals = []

		def mine(m, n, g, x):
			if m >= 0 and m < len(x) and (n >= 0) and (n < len(x[m])) and (x[m][n] > 0):
				g += x[m][n]
				backup = x[m][n]
				x[m][n] = 0
				mine(m + 1, n, g, x)
				mine(m - 1, n, g, x)
				mine(m, n + 1, g, x)
				mine(m, n - 1, g, x)
				x[m][n] = backup
			totals.append(g)
		for m in range(0, len(grid)):
			for n in range(0, len(grid[m])):
				mine(m, n, 0, grid)
		return max(totals)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(a, b, board, g, seen):
			nonlocal p
			p = max(p, g)
			for (i, j) in ((a + 1, b), (a - 1, b), (a, b + 1), (a, b - 1)):
				if 0 <= i < len(board) and 0 <= j < len(board[0]) and (board[i][j] != 0) and ((i, j) not in seen):
					seen.add((i, j))
					dfs(i, j, board, g + board[i][j], seen)
					seen.remove((i, j))
		p = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					dfs(i, j, grid, grid[i][j], {(i, j)})
		return p


class Solution:

	def __init__(self):
		self.max = 0

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				self.max = max(self.dfs(grid, i, j), self.max)
		return self.max

	def dfs(self, grid, i, j):
		if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[i])) or (grid[i][j] == 0):
			return 0
		temp = grid[i][j]
		grid[i][j] = 0
		up = temp + self.dfs(grid, i - 1, j)
		down = temp + self.dfs(grid, i + 1, j)
		left = temp + self.dfs(grid, i, j - 1)
		right = temp + self.dfs(grid, i, j + 1)
		grid[i][j] = temp
		return max(max(up, down), max(left, right))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(rl, cl) = (len(grid), len(grid[0]))
		de = ((1, 0), (0, 1), (-1, 0), (0, -1))

		def solve(x, y, seen):
			temp = 0
			for d in de:
				(nx, ny) = (x + d[0], y + d[1])
				if 0 <= nx < rl and 0 <= ny < cl and grid[nx][ny] and ((nx, ny) not in seen):
					temp = max(temp, solve(nx, ny, seen | {(x, y)}))
			return temp + grid[x][y]
		ans = 0
		for i in range(rl):
			for j in range(cl):
				if grid[i][j]:
					ans = max(ans, solve(i, j, set()))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def backtrack(grid, i, j):
			s = 0
			temp = grid[i][j]
			grid[i][j] = 0
			if i > 0 and grid[i - 1][j] != 0:
				s = max(s, backtrack(grid, i - 1, j))
			if i < len(grid) - 1 and grid[i + 1][j] != 0:
				s = max(s, backtrack(grid, i + 1, j))
			if j > 0 and grid[i][j - 1] != 0:
				s = max(s, backtrack(grid, i, j - 1))
			if j < len(grid[0]) - 1 and grid[i][j + 1] != 0:
				s = max(s, backtrack(grid, i, j + 1))
			grid[i][j] = temp
			return s + grid[i][j]
		ret = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					ret = max(ret, backtrack(grid, i, j))
		return ret


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		checked = set()
		maximum = 0
		for x in range(len(grid)):
			for y in range(len(grid[0])):
				if grid[x][y]:
					visited = set()
					value = self.recursive(0, x, y, grid, visited)
					if value > maximum:
						maximum = value
		return maximum

	def recursive(self, total, x, y, grid, visited):
		if grid[x][y] == 0:
			return total
		if (x, y) in visited:
			return total
		visited = set(visited)
		visited.add((x, y))
		total = total + grid[x][y]
		(left, right, top, btm) = (total, total, total, total)
		if x > 0:
			left = self.recursive(total, x - 1, y, grid, visited)
		if x < len(grid) - 1:
			right = self.recursive(total, x + 1, y, grid, visited)
		if y > 0:
			top = self.recursive(total, x, y - 1, grid, visited)
		if y < len(grid[x]) - 1:
			btm = self.recursive(total, x, y + 1, grid, visited)
		return max(left, right, top, btm, total)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(R, C) = (len(grid), len(grid[0]))

		def traverse(r, c):
			if not (0 <= r < R and 0 <= c < C):
				return 0
			if not grid[r][c]:
				return 0
			cur = grid[r][c]
			grid[r][c] = 0
			res = 0
			for (x, y) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
				res = max(res, traverse(r + x, c + y))
			res += cur
			grid[r][c] = cur
			return res
		result = 0
		for r in range(R):
			for c in range(C):
				result = max(result, traverse(r, c))
		return result


DIR = ((-1, 0), (1, 0), (0, -1), (0, 1))

class Solution:

	def getMaximumGold(self, grid):
		res = 0
		(m, n) = (len(grid), len(grid[0]))
		for x in range(m):
			for y in range(n):
				if grid[x][y] > 0:
					res = max(res, self.dfs(grid, x, y, {(x, y)}))
		return res

	def dfs(self, grid, x, y, visited):
		(m, n) = (len(grid), len(grid[0]))
		res = grid[x][y]
		for (dx, dy) in DIR:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx <= m - 1 and 0 <= ny <= n - 1 and (grid[nx][ny] > 0) and ((nx, ny) not in visited):
				visited.add((nx, ny))
				res = max(res, self.dfs(grid, nx, ny, visited) + grid[x][y])
				visited.remove((nx, ny))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.res = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				self.dfs(grid, i, j, 0)
		return self.res

	def dfs(self, grid, i, j, currSum):
		if i > len(grid) - 1 or i < 0 or j > len(grid[0]) - 1 or (j < 0):
			return
		if grid[i][j] == 0:
			return
		currSum += grid[i][j]
		temp = grid[i][j]
		grid[i][j] = 0
		self.dfs(grid, i - 1, j, currSum)
		self.dfs(grid, i, j - 1, currSum)
		self.dfs(grid, i + 1, j, currSum)
		self.dfs(grid, i, j + 1, currSum)
		grid[i][j] = temp
		self.res = max(self.res, currSum)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_gold = 0
		rows = len(grid)
		cols = len(grid[0])
		for row in range(rows):
			for col in range(cols):
				if grid[row][col] > 0:
					max_gold = max(max_gold, self.get_gold(grid, row, col))
		return max_gold

	def get_gold(self, grid, row, col):
		if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[row])) or (grid[row][col] == 0):
			return 0
		ori = grid[row][col]
		gold = 0
		grid[row][col] = 0
		gold = max(gold, self.get_gold(grid, row + 1, col))
		gold = max(gold, self.get_gold(grid, row - 1, col))
		gold = max(gold, self.get_gold(grid, row, col + 1))
		gold = max(gold, self.get_gold(grid, row, col - 1))
		grid[row][col] = ori
		return gold + ori


import copy

class Solution:

	def helper(self, grid, start_i, start_j, current_gold, visited):
		candidates = []
		current_gold += grid[start_i][start_j]
		visited[start_i, start_j] = 1
		if max(0, start_i - 1) != start_i and grid[start_i - 1][start_j] > 0 and ((start_i - 1, start_j) not in visited):
			candidates.append((start_i - 1, start_j))
		if min(len(grid) - 1, start_i + 1) != start_i and grid[start_i + 1][start_j] > 0 and ((start_i + 1, start_j) not in visited):
			candidates.append((start_i + 1, start_j))
		if max(0, start_j - 1) != start_j and grid[start_i][start_j - 1] > 0 and ((start_i, start_j - 1) not in visited):
			candidates.append((start_i, start_j - 1))
		if min(len(grid[0]) - 1, start_j + 1) != start_j and grid[start_i][start_j + 1] > 0 and ((start_i, start_j + 1) not in visited):
			candidates.append((start_i, start_j + 1))
		res = 0
		if not candidates:
			return current_gold
		for can in candidates:
			res = max(res, self.helper(grid, can[0], can[1], current_gold, dict(visited)))
		return res

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		res = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				start_i = i
				start_j = j
				counter = 0
				if max(0, start_i - 1) != start_i and grid[start_i - 1][start_j] > 0:
					counter += 1
				if min(len(grid) - 1, start_i + 1) != start_i and grid[start_i + 1][start_j] > 0:
					counter += 1
				if max(0, start_j - 1) != start_j and grid[start_i][start_j - 1] > 0:
					counter += 1
				if min(len(grid[0]) - 1, start_j + 1) != start_j and grid[start_i][start_j + 1] > 0:
					counter += 1
				if counter <= 2:
					dicts = {}
					res = max(res, self.helper(grid, i, j, 0, dicts))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		ans = [0]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					self.dfs(grid, i, j, [], ans)
		return ans[0]

	def dfs(self, grid, i, j, path, ans):
		if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == 0):
			return
		path.append(grid[i][j])
		grid[i][j] = 0
		ans[0] = max(ans[0], sum(path))
		self.dfs(grid, i + 1, j, path, ans)
		self.dfs(grid, i - 1, j, path, ans)
		self.dfs(grid, i, j + 1, path, ans)
		self.dfs(grid, i, j - 1, path, ans)
		grid[i][j] = path.pop()


import collections

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = 0
		start = []
		(cl, rl) = (len(grid[0]), len(grid))
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j]:
					start.append((i, j))
					if m < grid[i][j]:
						m = grid[i][j]
		ans = []
		for i in start:
			(r, c) = i
			s = str(r) + str(c)
			q = collections.deque()
			q.append([r, c, grid[r][c], s])
			while q:
				l = q.popleft()
				(r, c, s, path) = (l[0], l[1], l[2], l[3])
				lf = rf = uf = df = False
				if c - 1 >= 0 and grid[r][c - 1]:
					k = str(r) + str(c - 1)
					if k not in path:
						v = grid[r][c - 1]
						q.append([r, c - 1, s + v, path + '->' + k])
						lf = True
				if c + 1 < cl and grid[r][c + 1]:
					k = str(r) + str(c + 1)
					if k not in path:
						v = grid[r][c + 1]
						q.append([r, c + 1, s + v, path + '->' + k])
						rf = True
				if r - 1 >= 0 and grid[r - 1][c]:
					k = str(r - 1) + str(c)
					if k not in path:
						v = grid[r - 1][c]
						q.append([r - 1, c, s + v, path + '->' + k])
						uf = True
				if r + 1 < rl and grid[r + 1][c]:
					k = str(r + 1) + str(c)
					if k not in path:
						v = grid[r + 1][c]
						q.append([r + 1, c, s + v, path + '->' + k])
						df = True
				if not df and (not uf) and (not lf) and (not rf):
					ans.append(s)
		return max(ans)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.orig_grid = grid
		self.M = len(grid)
		self.N = len(grid[0])
		max_gold = 0
		for i in range(self.M):
			for j in range(self.N):
				self.soln = [[0 for j in range(self.N)] for i in range(self.M)]
				curr = self.trackGold(i, j)
				max_gold = max(max_gold, curr)
		return max_gold

	def trackGold(self, i, j):
		if i < 0 or i >= self.M or j < 0 or (j >= self.N) or (self.orig_grid[i][j] == 0) or (self.soln[i][j] == 1):
			return 0
		self.soln[i][j] = 1
		future_gold = max(self.trackGold(i + 1, j), self.trackGold(i, j + 1), self.trackGold(i - 1, j), self.trackGold(i, j - 1))
		curr_gold = self.orig_grid[i][j] + future_gold
		self.soln[i][j] = 0
		return curr_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		maxGold = 0
		(m, n) = (len(grid), len(grid[0]))

		def dfs(i, j):
			res = 0
			if grid[i][j] == 0:
				return 0
			tmp = grid[i][j]
			grid[i][j] = 0
			for (x, y) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
				if 0 <= x < m and 0 <= y < n:
					res = max(res, dfs(x, y))
			grid[i][j] = tmp
			return res + grid[i][j]
		for i in range(m):
			for j in range(n):
				maxGold = max(maxGold, dfs(i, j))
		return maxGold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_gold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j]:
					max_gold = max(max_gold, self.searchGrid(grid, i, j, 0))
		return max_gold

	def searchGrid(self, grid, i, j, gold):
		square_gold = grid[i][j]
		gold += square_gold
		grid[i][j] = 0
		up_gold = left_gold = down_gold = right_gold = gold
		if i > 0 and grid[i - 1][j]:
			up_gold = self.searchGrid(grid, i - 1, j, gold)
		if j > 0 and grid[i][j - 1]:
			left_gold = self.searchGrid(grid, i, j - 1, gold)
		if i < len(grid) - 1 and grid[i + 1][j]:
			down_gold = self.searchGrid(grid, i + 1, j, gold)
		if j < len(grid[0]) - 1 and grid[i][j + 1]:
			right_gold = self.searchGrid(grid, i, j + 1, gold)
		grid[i][j] = square_gold
		return max(up_gold, left_gold, down_gold, right_gold)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		l = len(grid)
		w = len(grid[0])
		seen = set()
		r = 0
		for x in grid:
			print(x)

		def dfs(x, y, gold):
			if (x, y) not in seen and 0 <= x < l and (0 <= y < w) and grid[x][y]:
				seen.add((x, y))
				gold += grid[x][y]
				dfs(x + 1, y, gold)
				dfs(x, y + 1, gold)
				dfs(x - 1, y, gold)
				dfs(x, y - 1, gold)
				seen.remove((x, y))
			else:
				nonlocal r
				r = max(r, gold)
		for i in range(l):
			for j in range(w):
				dfs(i, j, 0)
		return r


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.res = 0
		directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]

		def dfs(i, j, cur, grid):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == 0):
				return
			val = grid[i][j]
			grid[i][j] = 0
			self.res = max(self.res, cur + val)
			for (dx, dy) in directions:
				dfs(i + dx, j + dy, cur + val, grid)
			grid[i][j] = val
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				if grid[i][j] != 0:
					dfs(i, j, 0, grid)
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		res = [0]

		def bfs(v, x, y):
			seen.add((x, y))
			dp[x][y] = max(dp[x][y], v)
			for (i, j) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
				(a, b) = (x + i, y + j)
				if 0 <= a < m and 0 <= b < n and ((a, b) not in seen) and (grid[a][b] != 0):
					bfs(v + grid[a][b], a, b)
			seen.discard((x, y))
		dp = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					seen = set()
					bfs(grid[i][j], i, j)
		return max((max(row) for row in dp))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		result = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				result = max(self.search(grid, i, j, set()), result)
		return result

	def search(self, grid, x, y, visited):
		if x < 0 or x >= len(grid) or y < 0 or (y >= len(grid[0])):
			return 0
		if grid[x][y] == 0:
			return 0
		if (x, y) in visited:
			return 0
		result = grid[x][y]
		visited.add((x, y))
		result += max(self.search(grid, x - 1, y, visited), self.search(grid, x, y - 1, visited), self.search(grid, x + 1, y, visited), self.search(grid, x, y + 1, visited))
		visited.remove((x, y))
		return result


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_ = 0
		(n, m) = (len(grid), len(grid[0]))

		def backtrack(i, j, accum):
			nonlocal max_
			if grid[i][j] == 0:
				max_ = max(max_, accum)
				return
			(collected, grid[i][j]) = (grid[i][j], 0)
			accum += collected
			for (di, dj) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
				(try_i, try_j) = (i + di, j + dj)
				if 0 <= try_i < n and 0 <= try_j < m:
					backtrack(try_i, try_j, accum)
			grid[i][j] = collected
			accum -= collected
		for i in range(n):
			for j in range(m):
				backtrack(i, j, 0)
		return max_


class Solution:

	def __init__(self):
		self.next_moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(row, col):
			if grid[row][col] == 0:
				return 0
			gold = grid[row][col]
			grid[row][col] = 0
			max_child = 0
			for move in self.next_moves:
				(next_row, next_col) = (row + move[0], col + move[1])
				if -1 < next_row < n and -1 < next_col < m:
					max_child = max(max_child, dfs(next_row, next_col))
			grid[row][col] = gold
			return gold + max_child
		n = len(grid)
		m = len(grid[0])
		max_gold = 0
		for i in range(n):
			for j in range(m):
				max_gold = max(max_gold, dfs(i, j))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def findMaxGold(r: int, c: int) -> int:
			if r < 0 or r == m or c < 0 or (c == n) or (grid[r][c] == 0):
				return 0
			origin = grid[r][c]
			grid[r][c] = 0
			maxGold = 0
			for (nr, nc) in ((r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c)):
				maxGold = max(findMaxGold(nr, nc), maxGold)
			grid[r][c] = origin
			return maxGold + origin
		(m, n) = (len(grid), len(grid[0]))
		return max((findMaxGold(r, c) for c in range(n) for r in range(m)))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		d = [[-1, 0], [0, 1], [1, 0], [0, -1]]
		m = len(grid)
		if m == 0:
			return 0
		n = len(grid[0])
		visited = []
		visited_in = []
		for i in range(m):
			for j in range(n):
				visited_in.append(False)
			visited.append(visited_in)
			visited_in = []

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

		def DFS(grid, startx, starty):
			res = 0
			visited[startx][starty] = True
			for i in range(4):
				newx = startx + d[i][0]
				newy = starty + d[i][1]
				if inArea(newx, newy) and (not visited[newx][newy]) and (grid[newx][newy] != 0):
					res = max(res, grid[newx][newy] + DFS(grid, newx, newy))
			visited[startx][starty] = False
			return res
		maxRes = []
		record_each_result = []
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0 and (not visited[i][j]):
					result = grid[i][j] + DFS(grid, i, j)
					record_each_result.append(result)
		final_result = max(record_each_result)
		return final_result


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def collect(i, j):
			if not (0 <= i < m and 0 <= j < n and grid[i][j]):
				return 0
			(gold, grid[i][j]) = (grid[i][j], 0)
			choices = [collect(i + di, j + dj) for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]]
			grid[i][j] = gold
			return max(choices) + gold
		return max((collect(i, j) for i in range(m) for j in range(n)))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.ans = 0
		seen = set()
		delta = [(1, 0), (-1, 0), (0, -1), (0, 1)]

		def dfs(i, j, cur=0):
			for (di, dj) in delta:
				(new_i, new_j) = (i + di, j + dj)
				if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]):
					if (new_i, new_j) not in seen and grid[new_i][new_j]:
						seen.add((new_i, new_j))
						cur += grid[new_i][new_j]
						self.ans = max(self.ans, cur)
						dfs(new_i, new_j, cur)
						cur -= grid[new_i][new_j]
						seen.remove((new_i, new_j))
			return
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] and (i, j) not in seen:
					seen.add((i, j))
					self.ans = max(self.ans, grid[i][j])
					dfs(i, j, grid[i][j])
					seen.remove((i, j))
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def visit(i, j):
			visited[i][j] = True
			gold = 0
			if i > 0 and (not visited[i - 1][j]):
				gold = max(gold, visit(i - 1, j))
			if i < m - 1 and (not visited[i + 1][j]):
				gold = max(gold, visit(i + 1, j))
			if j > 0 and (not visited[i][j - 1]):
				gold = max(gold, visit(i, j - 1))
			if j < n - 1 and (not visited[i][j + 1]):
				gold = max(gold, visit(i, j + 1))
			visited[i][j] = False
			return gold + grid[i][j]
		visited = [[False] * n for i in range(m)]

		def reset():
			for i in range(m):
				for j in range(n):
					visited[i][j] = grid[i][j] == 0
		max_gold = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					reset()
					max_gold = max(max_gold, visit(i, j))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		visited = set()
		(m, n) = (len(grid), len(grid[0]))

		def isValid(x, y):
			return 0 <= x < m and 0 <= y < n
		dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]

		def dfs(x, y):
			if grid[x][y] == 0:
				return 0
			visited.add((x, y))
			ans = 0
			for (dx, dy) in dirs:
				if isValid(x + dx, y + dy) and (x + dx, y + dy) not in visited:
					ans = max(ans, dfs(x + dx, y + dy))
			visited.remove((x, y))
			return ans + grid[x][y]
		ans = 0
		for i in range(m):
			for j in range(n):
				ans = max(ans, dfs(i, j))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		rrange = range(len(grid))
		crange = range(len(grid[0]))
		max_sum = 0

		def helper(row, col, running_sum=0):
			nonlocal max_sum
			if not (row in rrange and col in crange and (grid[row][col] > 0)):
				max_sum = max(max_sum, running_sum)
				return
			running_sum += grid[row][col]
			grid[row][col] *= -1
			helper(row + 1, col, running_sum)
			helper(row, col + 1, running_sum)
			helper(row - 1, col, running_sum)
			helper(row, col - 1, running_sum)
			grid[row][col] *= -1
		for row in rrange:
			for col in crange:
				if grid[row][col] > 0:
					helper(row, col)
		return max_sum


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		numRows = len(grid)
		numCols = len(grid[0])
		self.maxResult = float('-inf')
		for r in range(numRows):
			for c in range(numCols):
				if grid[r][c] > 0:
					self._getMaxGoldHelper(grid, r, c, 0)
		return self.maxResult

	def _getMaxGoldHelper(self, grid, r, c, currSum):
		if r < 0 or c < 0 or r >= len(grid) or (c >= len(grid[0])) or (grid[r][c] <= 0):
			return
		currSum += grid[r][c]
		self.maxResult = max(self.maxResult, currSum)
		grid[r][c] *= -1
		for dir in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
			self._getMaxGoldHelper(grid, r + dir[0], c + dir[1], currSum)
		grid[r][c] *= -1


class Solution(object):

	def getMaximumGold(self, grid):
		self.ans = 0

		def helper(grid, i, j, s):
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j]:
				tmp = grid[i][j]
				grid[i][j] = 0
				helper(grid, i + 1, j, s + tmp)
				helper(grid, i - 1, j, s + tmp)
				helper(grid, i, j + 1, s + tmp)
				helper(grid, i, j - 1, s + tmp)
				grid[i][j] = tmp
			else:
				self.ans = max(self.ans, s)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j]:
					helper(grid, i, j, 0)
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.max_gold = 0
		self.row = len(grid)
		self.col = len(grid[0])
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j]:
					self.search_gold(grid, i, j, 0)
		return self.max_gold

	def search_gold(self, grid, i, j, val):
		pos = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		if i >= 0 and j >= 0 and (i < self.row) and (j < self.col) and grid[i][j]:
			temp = grid[i][j]
			val += grid[i][j]
			grid[i][j] = 0
			self.max_gold = max(self.max_gold, val)
			for (x, y) in pos:
				self.search_gold(grid, x + i, y + j, val)
			grid[i][j] = temp


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.dirs = ((1, 0), (0, 1), (-1, 0), (0, -1))
		self.nrow = len(grid)
		self.ncol = len(grid[0])
		max_gold = 0
		for i in range(self.nrow):
			for j in range(self.ncol):
				if grid[i][j] != 0:
					max_seen = self._dfs(grid, i, j, set())
					if max_seen > max_gold:
						max_gold = max_seen
		return max_gold

	def _dfs(self, grid, i, j, visited):
		child_max = []
		visited.add((i, j))
		for (dx, dy) in self.dirs:
			if 0 <= i + dx < self.nrow and 0 <= j + dy < self.ncol:
				if grid[i + dx][j + dy] != 0 and (i + dx, j + dy) not in visited:
					dir_sum = self._dfs(grid, i + dx, j + dy, visited)
					child_max.append(dir_sum)
		visited.remove((i, j))
		max_child = max(child_max) if child_max else 0
		return grid[i][j] + max_child


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		mx = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				mx = max(mx, self.helper(grid, i, j))
		return mx

	def helper(self, grid, i, j):
		if grid[i][j] == 0:
			return 0
		res = grid[i][j]
		newGrid = [row.copy() for row in grid]
		newGrid[i][j] = 0
		(up, down, left, right) = (0, 0, 0, 0)
		if i - 1 >= 0:
			up = self.helper(newGrid, i - 1, j)
		if i + 1 < len(grid):
			down = self.helper(newGrid, i + 1, j)
		if j - 1 >= 0:
			left = self.helper(newGrid, i, j - 1)
		if j + 1 < len(grid[0]):
			right = self.helper(newGrid, i, j + 1)
		res += max(up, down, left, right)
		return res


import copy

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.max = 0
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if grid[i][j] != 0:
					self.helper(grid, i, j, 0)
		return self.max

	def helper(self, grid, i, j, goldCount):
		if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (grid[i][j] == 0):
			self.max = max(self.max, goldCount)
			return
		goldCount += grid[i][j]
		val = grid[i][j]
		grid[i][j] = 0
		self.helper(grid, i + 1, j, goldCount)
		self.helper(grid, i - 1, j, goldCount)
		self.helper(grid, i, j + 1, goldCount)
		self.helper(grid, i, j - 1, goldCount)
		grid[i][j] = val


class Solution:

	def explore(self, grid, row, col):
		if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[0])) or (grid[row][col] == 0):
			return 0
		total = curr_gold = grid[row][col]
		max_gold = grid[row][col] = 0
		for (row_offset, col_offset) in ((-1, 0), (0, 1), (1, 0), (0, -1)):
			max_gold = max(max_gold, self.explore(grid, row + row_offset, col + col_offset))
		grid[row][col] = curr_gold
		return total + max_gold

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_gold = 0
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				max_gold = max(max_gold, self.explore(grid, row, col))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		self.max_gold = 0
		rows = len(grid)
		cols = len(grid[0])
		for row in range(rows):
			for col in range(cols):
				self.dfs(grid, row, col, 0)
		return self.max_gold

	def dfs(self, grid, row, col, gold):
		rows = len(grid)
		cols = len(grid[0])
		if row < 0 or row >= rows or col < 0 or (col >= cols) or (grid[row][col] == 0):
			return
		prev_gold = grid[row][col]
		grid[row][col] = 0
		gold += prev_gold
		self.max_gold = max(self.max_gold, gold)
		for (drow, dcol) in [(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)]:
			self.dfs(grid, drow, dcol, gold)
		grid[row][col] = prev_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def getMaxGold(y, x, gold):
			if y < 0 or y >= m or x < 0 or (x >= n) or (grid[y][x] == 0):
				return gold
			gold += grid[y][x]
			(origin, grid[y][x]) = (grid[y][x], 0)
			maxGold = 0
			for (ax, ay) in action:
				maxGold = max(getMaxGold(y + ay, x + ax, gold), maxGold)
			grid[y][x] = origin
			return maxGold
		action = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		(m, n) = (len(grid), len(grid[0]))
		return max((getMaxGold(y, x, 0) for x in range(n) for y in range(m)))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def dfs(x, y, visited, res):
			maxi = res[:]
			for (i, j) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
				if i >= 0 and i < m and (j >= 0) and (j < n) and (grid[i][j] > 0) and ((i, j) not in visited):
					visited.add((i, j))
					res.append(grid[i][j])
					result = dfs(i, j, visited, res)
					maxi = maxi if sum(maxi) > sum(result) else result
					res.pop()
					visited.remove((i, j))
			return maxi
		maxi = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] > 0:
					visited = set()
					res = []
					res.append(grid[i][j])
					visited.add((i, j))
					result = dfs(i, j, visited, res)
					maxi = max(maxi, sum(result))
		return maxi


class Solution:

	def _getMaximumGold(self, cur_sum, i, j, grid):
		m = len(grid)
		n = len(grid[0])
		max_sum = cur_sum
		if i + 1 < m and grid[i + 1][j] != 0:
			val = grid[i + 1][j]
			grid[i + 1][j] = 0
			temp_max_sum = self._getMaximumGold(cur_sum + val, i + 1, j, grid)
			grid[i + 1][j] = val
			if temp_max_sum > max_sum:
				max_sum = temp_max_sum
		if j + 1 < n and grid[i][j + 1] != 0:
			val = grid[i][j + 1]
			grid[i][j + 1] = 0
			temp_max_sum = self._getMaximumGold(cur_sum + val, i, j + 1, grid)
			grid[i][j + 1] = val
			if temp_max_sum > max_sum:
				max_sum = temp_max_sum
		if i - 1 >= 0 and grid[i - 1][j] != 0:
			val = grid[i - 1][j]
			grid[i - 1][j] = 0
			temp_max_sum = self._getMaximumGold(cur_sum + val, i - 1, j, grid)
			grid[i - 1][j] = val
			if temp_max_sum > max_sum:
				max_sum = temp_max_sum
		if j - 1 >= 0 and grid[i][j - 1] != 0:
			val = grid[i][j - 1]
			grid[i][j - 1] = 0
			temp_max_sum = self._getMaximumGold(cur_sum + val, i, j - 1, grid)
			grid[i][j - 1] = val
			if temp_max_sum > max_sum:
				max_sum = temp_max_sum
		return max_sum

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if grid is None:
			return 0
		m = len(grid)
		n = len(grid[0])
		total_max_sum = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 0:
					continue
				start = grid[i][j]
				grid[i][j] = 0
				max_sum = self._getMaximumGold(start, i, j, grid)
				if max_sum > total_max_sum:
					total_max_sum = max_sum
				grid[i][j] = start
		return total_max_sum


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_g = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 0:
					continue
				max_g = max(max_g, self.dfs(i, j, grid))
		return max_g

	def dfs(self, i, j, grid):
		if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == 0):
			return 0
		temp = grid[i][j]
		grid[i][j] = 0
		res = 0
		for (di, dj) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
			res = max(res, temp + self.dfs(i + di, j + dj, grid))
		grid[i][j] = temp
		return res


class Solution:

	def dfs(self, cur_gold, max_gold, grid, visited, i, j):
		if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (visited[i][j] == 1) or (grid[i][j] == 0):
			return
		visited[i][j] = 1
		self.dfs(cur_gold + grid[i][j], max_gold, grid, visited, i + 1, j)
		self.dfs(cur_gold + grid[i][j], max_gold, grid, visited, i - 1, j)
		self.dfs(cur_gold + grid[i][j], max_gold, grid, visited, i, j + 1)
		self.dfs(cur_gold + grid[i][j], max_gold, grid, visited, i, j - 1)
		max_gold[0] = max(max_gold[0], cur_gold + grid[i][j])
		visited[i][j] = 0

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		visited = [[0 for i in range(n)] for j in range(m)]
		res = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] > 0:
					max_gold = [0]
					visited = [[0 for i in range(n)] for j in range(m)]
					self.dfs(0, max_gold, grid, visited, i, j)
					res = max(res, max_gold[0])
		return res


class Solution:

	def maxgold(self, grid, i, j, visited={}):
		if 0 <= i and i < len(grid) and (j >= 0) and (j < len(grid[0])):
			if (i, j) not in visited or visited[i, j] == 0:
				visited[i, j] = 1
				if grid[i][j] != 0:
					value = grid[i][j] + max(self.maxgold(grid, i + 1, j, visited), self.maxgold(grid, i - 1, j, visited), self.maxgold(grid, i, j + 1, visited), self.maxgold(grid, i, j - 1, visited))
					visited[i, j] = 0
					return value
		return 0

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		val = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					candidate = self.maxgold(grid, i, j, {})
					if candidate > val:
						val = candidate
		return val


DIRECTIONS = [[1, 0], [-1, 0], [0, 1], [0, -1]]

class Solution:

	def dfs(self, grid, i, j, memo):
		if memo[i][j]:
			return 0
		memo[i][j] = True
		gold = 0
		for direction in DIRECTIONS:
			x = i + direction[0]
			y = j + direction[1]
			if x >= 0 and x < len(grid) and (y >= 0) and (y < len(grid[0])) and (grid[x][y] != 0):
				gold = max(gold, self.dfs(grid, x, y, memo))
		memo[i][j] = False
		return gold + grid[i][j]

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid or len(grid) == 0 or len(grid[0]) == 0:
			return 0
		max_gold = 0
		visited = [[0] * len(grid[0]) for _ in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 0 or visited[i][j]:
					continue
				max_gold = max(max_gold, self.dfs(grid, i, j, visited))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		output = 0
		direcs = [(0, -1), (-1, 0), (0, 1), (1, 0)]

		def dfs(i, j, gold, seen):
			nonlocal output
			if i < 0 or i == len(grid) or j < 0 or (j == len(grid[0])) or (grid[i][j] == 0):
				output = max(output, gold)
				return
			gold += grid[i][j]
			for (di, dj) in direcs:
				if (i + di, j + dj) not in seen:
					seen.add((i + di, j + dj))
					dfs(i + di, j + dj, gold, seen)
					seen.remove((i + di, j + dj))
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					dfs(i, j, 0, {(i, j)})
		return output


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		maxy = [0]
		print(grid)

		def gold(grid, summ, i, j):
			if i <= len(grid) - 1 and i > -1 and (j <= len(grid[0]) - 1) and (j > -1) and (grid[i][j] != 0):
				temp = grid[i][j]
				grid[i][j] = 0
				gold(grid, summ + temp, i + 1, j)
				gold(grid, summ + temp, i, j + 1)
				gold(grid, summ + temp, i - 1, j)
				gold(grid, summ + temp, i, j - 1)
				grid[i][j] = temp
			else:
				maxy[0] = max(maxy[0], summ)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					gold(grid, 0, i, j)
		return maxy[0]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.max_gold = 0

		def backtrack(grid, row, col, current):
			if 0 <= row < len(grid) and 0 <= col < len(grid[0]) and grid[row][col]:
				temp = grid[row][col]
				grid[row][col] = 0
				for (drow, dcol) in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
					backtrack(grid, row + drow, col + dcol, current + temp)
				grid[row][col] = temp
			else:
				self.max_gold = max(self.max_gold, current)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j]:
					backtrack(grid, i, j, 0)
		return self.max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i: int, j: int, visited: List[List[int]]) -> int:
			result = grid[i][j]
			for (x, y) in [[1, 0], [0, 1], [0, -1], [-1, 0]]:
				(n_x, n_y) = (i + x, j + y)
				if 0 <= n_x < len(grid) and 0 <= n_y < len(grid[0]) and grid[n_x][n_y] and (not visited[n_x][n_y]):
					visited[n_x][n_y] = 1
					child = dfs(n_x, n_y, visited)
					result = max(child + grid[i][j], result)
					visited[n_x][n_y] = 0
			return result
		total = 0
		visited = [[0] * len(grid[0]) for _ in range(len(grid))]
		for (i, row) in enumerate(grid):
			for (j, v) in enumerate(row):
				if (i > 0 and i < len(grid) - 1 and (grid[i - 1][j] > 0) and (grid[i + 1][j] > 0)) and grid[i][j]:
					pass
				elif grid[i][j]:
					visited[i][j] = 1
					total = max(dfs(i, j, visited), total)
					visited[i][j] = 0
		return total


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def max_gold(i, j):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == 0):
				return 0
			origin = grid[i][j]
			grid[i][j] = 0
			max_count = 0
			for (ni, nj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				max_count = max(max_gold(ni, nj), max_count)
			grid[i][j] = origin
			return max_count + origin
		mx = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				mx = max(mx, max_gold(i, j))
		return mx


class Solution:

	def __init__(self):
		self.EMPTY = 0
		self.DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		max_gold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != self.EMPTY:
					visited = set()
					visited.add((i, j))
					max_gold = max(max_gold, self.dfs(grid, i, j, visited))
		return max_gold

	def dfs(self, grid, i, j, visited):
		gold = 0
		for (delta_i, delta_j) in self.DIR:
			(next_i, next_j) = (i + delta_i, j + delta_j)
			if not self.inbound(grid, next_i, next_j) or (next_i, next_j) in visited or grid[next_i][next_j] == self.EMPTY:
				continue
			visited.add((next_i, next_j))
			gold = max(gold, self.dfs(grid, next_i, next_j, visited))
			visited.discard((next_i, next_j))
		return gold + grid[i][j]

	def inbound(self, grid, x, y):
		return 0 <= x < len(grid) and 0 <= y < len(grid[0])


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def nextPos(r, c):
			if r > 0:
				yield (r - 1, c)
			if r < m - 1:
				yield (r + 1, c)
			if c > 0:
				yield (r, c - 1)
			if c < n - 1:
				yield (r, c + 1)
		self.mx = 0

		def backtrack(r, c, visited, gold):
			self.mx = max(self.mx, gold)
			for (nr, nc) in nextPos(r, c):
				if not visited[nr][nc] and grid[nr][nc] > 0:
					gold += grid[nr][nc]
					visited[nr][nc] = True
					backtrack(nr, nc, visited, gold)
					gold -= grid[nr][nc]
					visited[nr][nc] = False
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				visited = [[False for _ in range(n)] for _ in range(m)]
				visited[i][j] = True
				if grid[i][j] > 0:
					backtrack(i, j, visited, grid[i][j])
		return self.mx


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		result = [float('-inf')]
		(m, n) = (len(grid), len(grid[0]))
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				self.backtrack(grid, i, j, m, n, visited, result, 0)
		return result[0]

	def isValid(self, grid, i, j, m, n, vis):
		return 0 <= i < m and 0 <= j < n and (grid[i][j] != 0) and (vis[i][j] == False)

	def backtrack(self, grid, i, j, m, n, vis, result, ttl):
		if self.isValid(grid, i, j, m, n, vis):
			newttl = ttl + grid[i][j]
			result[0] = max(result[0], newttl)
			vis[i][j] = True
			self.backtrack(grid, i - 1, j, m, n, vis, result, newttl)
			self.backtrack(grid, i, j - 1, m, n, vis, result, newttl)
			self.backtrack(grid, i + 1, j, m, n, vis, result, newttl)
			self.backtrack(grid, i, j + 1, m, n, vis, result, newttl)
			vis[i][j] = False


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def search(x, y):
			if x < 0 or x == len(grid) or y < 0 or (y == len(grid[0])) or (grid[x][y] == 0):
				return 0
			origin = grid[x][y]
			grid[x][y] = 0
			maxGold = 0
			for (nx, ny) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
				maxGold = max(maxGold, search(nx, ny))
			grid[x][y] = origin
			return maxGold + origin
		return max((search(i, j) for i in range(len(grid)) for j in range(len(grid[0]))))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		di = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					v = self.bfs(grid, i, j, di)
					ans = max(ans, v)
		return ans

	def bfs(self, A, r, c, di):
		q = collections.deque([[r, c, A[r][c], {(r, c)}]])
		mx = 0
		while q:
			(x, y, n, seen) = q.popleft()
			seen.add((x, y))
			mx = max(mx, n)
			for (i, j) in di:
				(nx, ny) = (x + i, y + j)
				if (nx, ny) not in seen and 0 <= nx < len(A) and (0 <= ny < len(A[0])) and (A[nx][ny] != 0):
					q.append([nx, ny, n + A[nx][ny], seen.copy()])
		return mx


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i: int, j: int, sum: int) -> int:
			if i < 0 or i >= m or j < 0 or (j >= n) or (not grid[i][j]) or (grid[i][j] > 100):
				return sum
			sum += grid[i][j]
			grid[i][j] += 1000
			mx = 0
			for (x, y) in ((i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)):
				mx = max(dfs(x, y, sum), mx)
			grid[i][j] -= 1000
			return mx
		(m, n) = (len(grid), len(grid[0]))
		return max((dfs(i, j, 0) for j in range(n) for i in range(m)))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(nrow, ncol) = (len(grid), len(grid[0]))

		def getMaximumGold_helper(grid, i, j):
			if i >= nrow or i < 0 or j >= ncol or (j < 0):
				return 0
			if grid[i][j] == 0:
				return 0
			cur = grid[i][j]
			grid[i][j] = 0
			res = cur + max(getMaximumGold_helper(grid, i, j + 1), getMaximumGold_helper(grid, i, j - 1), getMaximumGold_helper(grid, i + 1, j), getMaximumGold_helper(grid, i - 1, j))
			grid[i][j] = cur
			return res
		max_gold = 0
		for i in range(nrow):
			for j in range(ncol):
				cur_gold = getMaximumGold_helper(grid, i, j)
				max_gold = max(max_gold, cur_gold)
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					ans = max(ans, self.findGold(grid, i, j))
		return ans

	def findGold(self, grid, row, col):
		if not (0 <= row < len(grid) and 0 <= col < len(grid[0])) or grid[row][col] == 0:
			return 0
		ans = 0
		temp = grid[row][col]
		grid[row][col] = 0
		for (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			ans = max(ans, self.findGold(grid, row + i, col + j))
		grid[row][col] = temp
		return ans + temp


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(R, C) = (len(grid), len(grid[0]))
		self.visited = [[False] * C for _ in range(R)]
		ans = 0

		def dfs(grid, r, c, R, C):
			if r < 0 or c < 0 or r >= R or (c >= C) or self.visited[r][c] or (grid[r][c] == 0):
				return 0
			self.visited[r][c] = True
			max_ = max(dfs(grid, r - 1, c, R, C), dfs(grid, r + 1, c, R, C), dfs(grid, r, c - 1, R, C), dfs(grid, r, c + 1, R, C)) + grid[r][c]
			self.visited[r][c] = False
			return max_
		for r in range(R):
			for c in range(C):
				ans = max(ans, dfs(grid, r, c, R, C))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		marked = [[False] * len(grid[0]) for i in range(len(grid))]
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] == 0:
					marked[r][c] = True

		def visit(r, c, markL):
			if r < 0 or c < 0 or r >= len(grid) or (c >= len(grid[0])):
				return 0
			if markL[r][c]:
				return 0
			copy = list(map(list, markL))
			copy[r][c] = True
			return grid[r][c] + max(visit(r + 1, c, copy), visit(r - 1, c, copy), visit(r, c - 1, copy), visit(r, c + 1, copy))
		maximum = -1
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if not marked[r][c]:
					maximum = max(maximum, visit(r, c, marked))
		print(marked)
		return maximum


DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

class Solution:

	def getMaximumGold(self, grid):
		(m, n) = (len(grid), len(grid[0]))

		def dfs(i, j, seen):
			if i >= m or i < 0 or j >= n or (j < 0) or ((i, j) in seen) or (grid[i][j] == 0):
				return 0
			gold = 0
			seen.add((i, j))
			for (i_inc, j_inc) in DIRS:
				(ni, nj) = (i + i_inc, j + j_inc)
				gold = max(gold, dfs(ni, nj, seen))
			seen.remove((i, j))
			return gold + grid[i][j]
		res = 0
		for i in range(m):
			for j in range(n):
				res = max(res, dfs(i, j, set()))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def findMaxGold(grid, i, j):
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] > 0):
				origin = grid[i][j]
				grid[i][j] = 0
				d = [(1, 0), (0, -1), (-1, 0), (0, 1)]
				maxGold = 0
				for (d1, d2) in d:
					maxGold = max(maxGold, findMaxGold(grid, i + d1, j + d2))
				grid[i][j] = origin
				return origin + maxGold
			else:
				return 0
		maxGold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				maxGold = max(maxGold, findMaxGold(grid, i, j))
		return maxGold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		(m, n) = (len(grid), len(grid[0]))
		result = 0
		best_path = set()

		def dfs(i, j, visited, res):
			nonlocal result, best_path
			if res > result:
				best_path = visited
				result = res
			for (a, b) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				(ci, cj) = (a + i, b + j)
				if 0 <= ci < m and 0 <= cj < n and ((ci, cj) not in visited) and (grid[ci][cj] != 0):
					dfs(ci, cj, visited | set([(ci, cj)]), res + grid[ci][cj])
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0 and (i, j) not in best_path:
					dfs(i, j, set([(i, j)]), grid[i][j])
		return result


class Solution:

	def getDegree(self, i, j, grid: List[List[int]]) -> int:
		deg = 0
		if i > 0 and grid[i - 1][j] > 0:
			deg += 1
		if i < len(grid) - 1 and grid[i + 1][j] > 0:
			deg += 1
		if j > 0 and grid[i][j - 1] > 0:
			deg += 1
		if j < len(grid[0]) - 1 and grid[i][j + 1] > 0:
			deg += 1
		return deg

	def traverseMaxGoldDfs(self, i, j, grid) -> int:
		degree = self.getDegree(i, j, grid)
		if degree == 0:
			return grid[i][j]
		temp = grid[i][j]
		grid[i][j] = 0
		gold = temp
		res = 0
		if i > 0 and grid[i - 1][j] > 0:
			res = max(res, self.traverseMaxGoldDfs(i - 1, j, grid))
		if i < len(grid) - 1 and grid[i + 1][j] > 0:
			res = max(res, self.traverseMaxGoldDfs(i + 1, j, grid))
		if j > 0 and grid[i][j - 1] > 0:
			res = max(res, self.traverseMaxGoldDfs(i, j - 1, grid))
		if j < len(grid[0]) - 1 and grid[i][j + 1] > 0:
			res = max(res, self.traverseMaxGoldDfs(i, j + 1, grid))
		gold = max(gold, temp + res)
		grid[i][j] = temp
		return gold

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		maxGold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				degree = self.getDegree(i, j, grid)
				if grid[i][j] > 0 and (degree <= 1 or degree > 2):
					gold = self.traverseMaxGoldDfs(i, j, grid)
					if gold > maxGold:
						maxGold = gold
		return maxGold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		R = len(grid)
		C = len(grid[0])
		self.res = 0

		def backtrack(i, j, cur_gold):
			self.res = max(self.res, cur_gold)
			if 0 <= i < R and 0 <= j < C and (grid[i][j] != 0):
				gold = grid[i][j]
				grid[i][j] = 0
				backtrack(i + 1, j, cur_gold + gold)
				backtrack(i - 1, j, cur_gold + gold)
				backtrack(i, j + 1, cur_gold + gold)
				backtrack(i, j - 1, cur_gold + gold)
				grid[i][j] = gold
		for i in range(R):
			for j in range(C):
				if grid[i][j] != 0:
					backtrack(i, j, 0)
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		visited = set()

		def DFS(i, j, sum):
			if i < 0 or i == m or j < 0 or (j == n) or (grid[i][j] == 0) or (grid[i][j] > 100):
				return sum
			sum += grid[i][j]
			grid[i][j] += 101
			maxi = 0
			for (x, y) in [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]:
				maxi = max(maxi, DFS(x, y, sum))
			grid[i][j] -= 101
			return maxi
		return max((DFS(i, j, 0) for i in range(m) for j in range(n) if grid[i][j] != 0))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i: int, j: int, sum_so_far: int, seen: set) -> int:
			if i < 0 or i >= m or j < 0 or (j >= n) or (not grid[i][j]) or ((i, j) in seen):
				return sum_so_far
			seen.add((i, j))
			sum_so_far += grid[i][j]
			mx = 0
			for (x, y) in ((i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)):
				mx = max(dfs(x, y, sum_so_far, seen), mx)
			seen.discard((i, j))
			return mx
		(m, n) = (len(grid), len(grid[0]))
		all_gold_path = []
		for row in range(m):
			for col in range(n):
				all_gold_path.append(dfs(row, col, 0, set()))
		return max(all_gold_path)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i, j, runsum):
			runsum += grid[i][j]
			visited[i][j] = 1
			dirr = [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]
			for (r, c) in dirr:
				if r >= 0 and r < len(grid) and (c >= 0) and (c < len(grid[0])):
					if visited[r][c] == 0 and grid[r][c] != 0:
						dfs(r, c, runsum)
			visited[i][j] = 0
			runningmax.append(runsum)

		def getCleanVisited():
			visited = []
			for i in range(len(grid)):
				visited.append([])
				for j in range(len(grid[0])):
					visited[i].append(0)
			return visited
		overallmax = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				visited = getCleanVisited()
				runningmax = []
				dfs(i, j, 0)
				overallmax = max(overallmax, max(runningmax))
		return overallmax


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(nrow, ncol) = (len(grid), len(grid[0]))
		max_len = 0

		def dfs(trajectory, r, c):
			nonlocal max_len
			count_neighbor = 0
			for (dr, dc) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
				(nr, nc) = (r + dr, c + dc)
				if 0 <= nr < nrow and 0 <= nc < ncol and (grid[nr][nc] != 0) and ((nr, nc) not in trajectory):
					count_neighbor += 1
					trajectory.add((nr, nc))
					dfs(trajectory, nr, nc)
					trajectory.remove((nr, nc))
			if count_neighbor == 0:
				max_len = max(max_len, sum((grid[i][j] for (i, j) in trajectory)))
		max_len = 0
		for r in range(nrow):
			for c in range(ncol):
				if grid[r][c] != 0:
					dfs(set([(r, c)]), r, c)
		return max_len


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(grid_height, grid_width) = (len(grid), len(grid[0]))
		visited = set()

		def helper(i, j, gold=0):
			if i < 0 or i >= grid_height or j < 0 or (j >= grid_width) or ((i, j) in visited) or (grid[i][j] == 0):
				return gold
			visited.add((i, j))
			res = 0
			for (a, b) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				res = max(helper(i + a, j + b, gold + grid[i][j]), res)
			visited.remove((i, j))
			return res
		return max((helper(i, j) for i in range(grid_height) for j in range(grid_width)))


class Solution:

	def getMaximumGold(self, A: List[List[int]]) -> int:

		def dfs(i, j):
			if not (0 <= i < m and 0 <= j < n):
				return 0
			if A[i][j] == 0:
				return 0
			if (i, j) in path:
				return 0
			path.add((i, j))
			gold = 0
			for (ni, nj) in ((i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)):
				gold = max(gold, dfs(ni, nj))
			path.discard((i, j))
			return A[i][j] + gold
		ans = 0
		maxpath = set()
		path = set()
		(m, n) = (len(A), len(A[0]))
		for i in range(m):
			for j in range(n):
				if (i, j) in maxpath:
					pass
				gold = dfs(i, j)
				if gold > ans:
					ans = gold
				path.clear()
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(grid, i, j):
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] != 0):
				temp = grid[i][j]
				grid[i][j] = 0
				d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
				summax = 0
				for (m, n) in d:
					x = i + m
					y = j + n
					summax = max(summax, dfs(grid, x, y))
				grid[i][j] = temp
				return temp + summax
			else:
				return 0
		res = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				res = max(res, dfs(grid, i, j))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		checked = set()
		maximum = 0
		for x in range(len(grid)):
			for y in range(len(grid[0])):
				if grid[x][y] and (x, y) not in checked:
					visited = set()
					value = self.recursive(0, x, y, grid, visited, checked)
					if value > maximum:
						maximum = value
		return maximum

	def valid(self, x, y, grid, visited):
		if grid[x][y] == 0 or (x, y) in visited:
			return False
		return True

	def recursive(self, total, x, y, grid, visited, checked):
		if not self.valid(x, y, grid, visited):
			return total
		visited = set(visited)
		visited.add((x, y))
		total = total + grid[x][y]
		(left, right, top, btm) = (total, total, total, total)
		if x > 0:
			left = self.recursive(total, x - 1, y, grid, visited, checked)
		if x < len(grid) - 1:
			right = self.recursive(total, x + 1, y, grid, visited, checked)
		if y > 0:
			top = self.recursive(total, x, y - 1, grid, visited, checked)
		if y < len(grid[x]) - 1:
			btm = self.recursive(total, x, y + 1, grid, visited, checked)
		return max(left, right, top, btm, total)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		visited = [[False for _ in range(n)] for _ in range(m)]
		self.ans = -1

		def helper(i, j):
			if i >= m or j >= n or i < 0 or (j < 0) or (grid[i][j] == 0) or visited[i][j]:
				return 0
			visited[i][j] = True
			a = helper(i, j + 1)
			b = helper(i, j - 1)
			c = helper(i + 1, j)
			d = helper(i - 1, j)
			total = grid[i][j] + max(max(max(a, b), c), d)
			visited[i][j] = False
			return total
		for i in range(m):
			for j in range(n):
				self.ans = max(self.ans, helper(i, j))
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(pos):
			if grid[pos[0]][pos[1]] == 0:
				return 0
			gold = grid[pos[0]][pos[1]]
			grid[pos[0]][pos[1]] = 0
			next_pos = [(pos[0] - 1, pos[1]), (pos[0] + 1, pos[1]), (pos[0], pos[1] - 1), (pos[0], pos[1] + 1)]
			max_child = 0
			for p in next_pos:
				if -1 < p[0] < n and -1 < p[1] < m:
					max_child = max(max_child, dfs(p))
			grid[pos[0]][pos[1]] = gold
			return gold + max_child
		n = len(grid)
		m = len(grid[0])
		max_gold = 0
		for i in range(n):
			for j in range(m):
				max_gold = max(max_gold, dfs((i, j)))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i, j, vis):
			res = 0
			for (z1, z2) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				(x, y) = (i + z1, j + z2)
				if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and ((x, y) not in vis) and (grid[x][y] != 0):
					vis.add((x, y))
					res = max(res, dfs(x, y, vis))
					vis.remove((x, y))
			return res + grid[i][j]

		def check(i, j):
			if i == 0 or j == 0 or i == len(grid) - 1 or (j == len(grid[0]) - 1):
				return True
			cnt = 0
			for (z1, z2) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				(x, y) = (i + z1, j + z2)
				if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (grid[x][y] != 0):
					cnt += 1
			if cnt <= 1:
				return True
			return False
		res = 0
		if not grid or not grid[0]:
			return res
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0 and check(i, j):
					vis = set()
					vis.add((i, j))
					ans = dfs(i, j, vis)
					res = max(res, ans)
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def is_valid(i, j):
			if 0 <= i < m and 0 <= j < n:
				return True
			return False

		def dfs(i, j, visited, cur_sum):
			visited.add((i, j))
			cur_sum += grid[i][j]
			cur_max = 0
			for d in directions:
				(ni, nj) = (i + d[0], j + d[1])
				if is_valid(ni, nj) and (ni, nj) not in visited and (grid[ni][nj] > 0):
					cur_max = max(cur_max, dfs(ni, nj, visited, cur_sum))
				else:
					cur_max = max(cur_max, cur_sum)
			visited.discard((i, j))
			return cur_max
		(m, n) = (len(grid), len(grid[0]))
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		max_gold = 0
		visited = set()
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					max_gold = max(max_gold, dfs(i, j, set(), 0))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def travel(grid, x, y, gold):

			def valid(c, grid):
				(x, y) = c
				if x < 0 or x > len(grid) - 1 or y < 0 or (y > len(grid[0]) - 1) or (grid[x][y] == 0):
					return False
				return True
			dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
			g = grid[x][y]
			grid[x][y] = 0
			maxg = -1
			for i in dirs:
				nc = (x + i[0], y + i[1])
				if valid(nc, grid):
					maxg = max(maxg, travel(grid, nc[0], nc[1], gold + g))
			grid[x][y] = g
			if maxg == -1:
				return gold + g
			return maxg
		maxg = 0
		for (ri, row) in enumerate(grid):
			for (ci, e) in enumerate(row):
				if e != 0:
					k = travel(grid, ri, ci, 0)
					maxg = max(maxg, k)
		return maxg


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		ans = 0
		row = len(grid)
		if not row:
			return 0
		col = len(grid[0])
		if not col:
			return 0
		dc = [0, 1, 0, -1]
		dr = [-1, 0, 1, 0]

		def dfs(i, j):
			if i < 0 or i >= row or j < 0 or (j >= col) or (grid[i][j] < 1):
				return 0
			t = 0
			grid[i][j] = -grid[i][j]
			for d in range(4):
				t = max(t, dfs(i + dr[d], j + dc[d]))
			grid[i][j] = -grid[i][j]
			return t + grid[i][j]
		for i in range(row):
			for j in range(col):
				if grid[i][j]:
					gold = dfs(i, j)
					ans = max(gold, ans)
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(row, col) = (len(grid), len(grid[0]))
		maxgold = 0
		directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

		def collectgold(r, c, path, tot):
			nonlocal maxgold
			tot += grid[r][c]
			if tot > maxgold:
				maxgold = tot
			for (x, y) in directions:
				if 0 <= r + x < row and 0 <= c + y < col and ((r + x, c + y) not in path) and grid[r + x][c + y]:
					collectgold(r + x, c + y, path + [(r + x, c + y)], tot)
		for i in range(row):
			for j in range(col):
				if grid[i][j]:
					collectgold(i, j, [(i, j)], 0)
		return maxgold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.maxX = len(grid[0]) - 1
		self.maxY = len(grid) - 1
		self.maxGold = 0
		for y in range(0, len(grid)):
			for x in range(0, len(grid[0])):
				if grid[y][x] != 0:
					self.helper(x, y, grid, 0)
		return self.maxGold

	def helper(self, x, y, grid, gold):
		gold += grid[y][x]
		left = 0 if x - 1 < 0 else grid[y][x - 1]
		right = 0 if x + 1 > self.maxX else grid[y][x + 1]
		top = 0 if y - 1 < 0 else grid[y - 1][x]
		bottom = 0 if y + 1 > self.maxY else grid[y + 1][x]
		if left == 0 and right == 0 and (top == 0) and (bottom == 0):
			if gold > self.maxGold:
				self.maxGold = gold
			return
		tmp = grid[y][x]
		grid[y][x] = 0
		if left != 0:
			self.helper(x - 1, y, grid, gold)
		if right != 0:
			self.helper(x + 1, y, grid, gold)
		if top != 0:
			self.helper(x, y - 1, grid, gold)
		if bottom != 0:
			self.helper(x, y + 1, grid, gold)
		grid[y][x] = tmp


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		final = [0]
		visited = set()
		directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]

		def bt(current_sum=0, i=0, j=0):
			if (i, j) in visited or i < 0 or i >= len(grid) or (j < 0) or (j >= len(grid[0])) or (grid[i][j] == 0):
				final[0] = max(final[0], current_sum)
				return
			current_sum += grid[i][j]
			visited.add((i, j))
			for direction in directions:
				new_i = i + direction[0]
				new_j = j + direction[1]
				bt(current_sum, new_i, new_j)
			visited.remove((i, j))
			current_sum -= grid[i][j]
		for row in range(len(grid)):
			for col in range(len(grid[row])):
				bt(i=row, j=col)
		return final[0]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		N = len(grid)
		M = len(grid[0])

		def dfs(src, seen, pSum):
			(curI, curJ) = (src[0], src[1])
			if (curI, curJ) not in seen and curI >= 0 and (curI < N) and (curJ >= 0) and (curJ < M) and (grid[curI][curJ] != 0):
				seen.add((curI, curJ))
				pSum += grid[curI][curJ]
				self.sol = max(self.sol, pSum)
				for d in direction:
					(nI, nJ) = (curI + d[0], curJ + d[1])
					dfs((nI, nJ), seen, pSum)
				seen.remove((curI, curJ))
		self.sol = -1
		for i in range(N):
			for j in range(M):
				if grid[i][j] != 0:
					seen = set()
					dfs((i, j), seen, 0)
		return self.sol


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		p = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] != 0:
					p = max(p, self.dfs(grid, i, j, m, n))
		return p

	def dfs(self, grid, starti, startj, m, n):
		visited = [[0 for i in range(m)] for j in range(n)]
		return self.dfsUtil(grid, starti, startj, visited, m, n)

	def dfsUtil(self, grid, i, j, visited, m, n):
		ct = grid[i][j]
		k = 0
		if visited[i][j] == 0 and grid[i][j] != 0:
			visited[i][j] = 1
			neighbours = [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]
			for neighbour in neighbours:
				if neighbour[0] >= 0 and neighbour[0] < n and (neighbour[1] >= 0) and (neighbour[1] < m):
					k = max(k, self.dfsUtil(grid, neighbour[0], neighbour[1], visited, m, n))
			visited[i][j] = 0
			return ct + k
		else:
			return 0


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def walk(grid, i, j):
			nonlocal m, n
			if not grid or i < 0 or i >= m or (j < 0) or (j >= n):
				return 0
			if grid[i][j] < 1:
				return 0
			g = []
			for k in range(m):
				g.append(grid[k][:])
			ans = grid[i][j]
			g[i][j] = 0
			ans += max(walk(g, i - 1, j), walk(g, i + 1, j), walk(g, i, j - 1), walk(g, i, j + 1))
			return ans
		ans = 0
		for i in range(m):
			for j in range(n):
				ans = max(ans, walk(grid, i, j))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(r, c) = (len(grid), len(grid[0]))
		self.res = 0
		dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

		def dfs(i, j, curr):
			self.res = max(self.res, curr)
			if i < r and j < c and (i >= 0) and (j >= 0) and (grid[i][j] != 0):
				gold = grid[i][j]
				for (x, y) in dirs:
					grid[i][j] = 0
					dfs(i + x, j + y, curr + gold)
					grid[i][j] = gold
		for i in range(r):
			for j in range(c):
				if grid[i][j] != 0:
					dfs(i, j, 0)
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		values = [[0 for j in range(0, m)] for i in range(0, n)]
		visited = [[0 for j in range(0, m)] for i in range(0, n)]
		_max = 0
		for i in range(0, n):
			for j in range(0, m):
				if grid[i][j] != 0:
					self._clear(visited)
					values[i][j] = self._dfs(i, j, grid, visited)
					_max = max(_max, values[i][j])
		return _max

	def _clear(self, grid: List[List[int]]) -> None:
		n = len(grid)
		m = len(grid[0])
		for i in range(0, n):
			for j in range(0, m):
				grid[i][j] = 0

	def _dfs(self, i: int, j: int, grid: List[List[int]], visited: List[List[int]]) -> int:
		if grid[i][j] == 0:
			return 0
		if visited[i][j] != 0:
			return 0
		n = len(grid)
		m = len(grid[0])
		visited[i][j] = 1
		idx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		_max = 0
		for p in idx:
			if i + p[0] >= 0 and i + p[0] < n and (j + p[1] >= 0) and (j + p[1] < m):
				v = self._dfs(i + p[0], j + p[1], grid, visited)
				_max = max(_max, v)
		visited[i][j] = 0
		return grid[i][j] + _max


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(row, col, curgold):
			if 0 <= row < len(grid) and 0 <= col < len(grid[0]) and (grid[row][col] > 0):
				temp = grid[row][col]
				grid[row][col] = 0
				dfs(row + 1, col, curgold + temp)
				dfs(row - 1, col, curgold + temp)
				dfs(row, col + 1, curgold + temp)
				dfs(row, col - 1, curgold + temp)
				self.maxgold = max(self.maxgold, curgold + temp)
				grid[row][col] = temp
		self.maxgold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					dfs(i, j, 0)
		return self.maxgold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def goDfsGo(row, col):
			ret_max = 0
			temp_val = grid[row][col]
			grid[row][col] = False
			if row + 1 < len(grid) and grid[row + 1][col] != False and (grid[row + 1][col] != 0):
				ret_max = max(ret_max, temp_val + goDfsGo(row + 1, col))
			if row - 1 >= 0 and grid[row - 1][col] != False and (grid[row - 1][col] != 0):
				ret_max = max(ret_max, temp_val + goDfsGo(row - 1, col))
			if col + 1 < len(grid[0]) and grid[row][col + 1] != False and (grid[row][col + 1] != 0):
				ret_max = max(ret_max, temp_val + goDfsGo(row, col + 1))
			if col - 1 >= 0 and grid[row][col - 1] != False and (grid[row][col - 1] != 0):
				ret_max = max(ret_max, temp_val + goDfsGo(row, col - 1))
			grid[row][col] = temp_val
			return max(ret_max, grid[row][col])
		mah_max = 0
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if grid[row][col] != 0:
					mah_max = max(mah_max, goDfsGo(row, col))
		return mah_max


class Solution:

	def getNeighbors(self, root, grid):
		deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		(x, y) = root
		return [(x + dx, y + dy) for (dx, dy) in deltas if 0 <= x + dx < len(grid) and 0 <= y + dy < len(grid[x])]

	def dfs(self, root, grid, visited):
		if root in visited:
			return 0
		visited.add(root)
		gold = 0
		for (nx, ny) in self.getNeighbors(root, grid):
			if (nx, ny) in visited:
				continue
			if grid[nx][ny] == 0:
				continue
			gold = max(gold, self.dfs((nx, ny), grid, visited))
		visited.remove(root)
		return gold + grid[root[0]][root[1]]

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		maxGold = 0
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j] == 0:
					continue
				maxGold = max(maxGold, self.dfs((i, j), grid, set()))
		return maxGold
[[0, 0, 19, 5, 8], [11, 20, 14, 1, 0], [0, 0, 1, 1, 1], [0, 2, 0, 2, 0]]


class Solution:

	def dfs(self, pos, sum):
		if pos in self.visit or pos[0] < 0 or pos[0] >= self.M or (pos[1] < 0) or (pos[1] >= self.N) or (not self.grid[pos[0]][pos[1]]):
			return
		self.visit.add(pos)
		sum += self.grid[pos[0]][pos[1]]
		(x, y) = pos
		self.maxGold = max(self.maxGold, sum)
		[self.dfs(node, sum) for node in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]]
		self.visit.remove(pos)

	def getMaximumGold(self, grid: List[List[int]]):
		self.maxGold = 0
		self.M = len(grid)
		self.N = len(grid[0])
		self.grid = grid
		for beginX in range(self.M):
			for beginY in range(self.N):
				if grid[beginX][beginY] > 0:
					self.visit = set()
					self.dfs((beginX, beginY), 0)
		return self.maxGold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def initVisit(m, n):
			visited = {}
			for i in range(m):
				for j in range(n):
					visited[i, j] = -1
			return visited
		maxGold = 0

		def check(i, j):
			if 0 <= i < m and 0 <= j < n and (grid[i][j] != 0) and (visited[i, j] != 1):
				return True
			else:
				return False

		def helper(i, j):
			moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]
			maxSum = 0
			for move in moves:
				(nextI, nextJ) = (move[0] + i, move[1] + j)
				if check(nextI, nextJ):
					visited[i, j] = 1
					maxSum = max(maxSum, helper(nextI, nextJ))
					visited[i, j] = 0
			return maxSum + grid[i][j]
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					visited = initVisit(m, n)
					visited[i, j] = 1
					maxGold = max(maxGold, helper(i, j))
		return maxGold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		out = 0
		for (y, row) in enumerate(grid):
			for (x, val) in enumerate(row):
				if val != 0:
					cur_max = max_collect(x, y, grid)
					out = max(out, cur_max)
		return out

def max_collect(x, y, grid, visited=set([])):
	if y < 0 or y >= len(grid):
		return 0
	if x < 0 or x >= len(grid[y]):
		return 0
	if grid[y][x] == 0:
		return 0
	if (x, y) in visited:
		return 0
	visited.add((x, y))
	_max = 0
	for (xx, yy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
		_max = max(_max, max_collect(xx, yy, grid, visited))
	visited.remove((x, y))
	return _max + grid[y][x]


def is_valid_cell(row, col, rows, cols):
	return 0 <= row < rows and 0 <= col < cols

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		rows = len(grid)
		cols = len(grid[0])
		max_amount = 0

		def backtrack(row, col, rows, cols, grid):
			if not is_valid_cell(row, col, rows, cols) or grid[row][col] == 0:
				return 0
			directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
			original = grid[row][col]
			grid[row][col] = 0
			max_sum = 0
			for (dr, dc) in directions:
				r = row + dr
				c = col + dc
				max_sum = max(max_sum, backtrack(r, c, rows, cols, grid))
			grid[row][col] = original
			return original + max_sum
		for row in range(rows):
			for col in range(cols):
				ans = backtrack(row, col, rows, cols, grid)
				max_amount = max(max_amount, ans)
		return max_amount


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		max_gold = 0
		for row in range(m):
			for col in range(n):
				max_gold = max(max_gold, self.findMaxGold(grid, row, col, 0))
		return max_gold

	def findMaxGold(self, grid, row, col, curr_gold):
		if 0 <= row < len(grid) and 0 <= col < len(grid[0]) and (grid[row][col] != 0):
			origin = grid[row][col]
			grid[row][col] = 0
			max_gold = 0
			x_moves = [1, -1, 0, 0]
			y_moves = [0, 0, 1, -1]
			for i in range(0, 4):
				max_gold = max(max_gold, self.findMaxGold(grid, row + x_moves[i], col + y_moves[i], max_gold))
			grid[row][col] = origin
			return max_gold + origin
		else:
			return 0


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(row, col, visited):
			if (row, col) in visited or grid[row][col] == 0:
				return 0
			next_visited = visited | set([(row, col)])
			next_pos = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
			max_child = 0
			for (next_row, next_col) in next_pos:
				if -1 < next_row < n and -1 < next_col < m:
					max_child = max(max_child, dfs(next_row, next_col, next_visited))
			return grid[row][col] + max_child
		n = len(grid)
		m = len(grid[0])
		max_gold = 0
		for i in range(n):
			for j in range(m):
				max_gold = max(max_gold, dfs(i, j, set()))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		grid_visited = [[0 for i in range(n)] for i in range(m)]
		max_gold = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					temp = self.start_mine(grid, grid_visited, i, j)
					max_gold = max(max_gold, temp)
		return max_gold

	def start_mine(self, grid, grid_visited, i, j):
		total = grid[i][j]
		max_choice = 0
		grid_visited[i][j] = 1
		if i - 1 >= 0 and grid[i - 1][j] != 0 and (grid_visited[i - 1][j] == 0):
			temp = self.start_mine(grid, grid_visited, i - 1, j)
			max_choice = max(temp, max_choice)
		if i + 1 < len(grid) and grid[i + 1][j] != 0 and (grid_visited[i + 1][j] == 0):
			temp = self.start_mine(grid, grid_visited, i + 1, j)
			max_choice = max(temp, max_choice)
		if j - 1 >= 0 and grid[i][j - 1] != 0 and (grid_visited[i][j - 1] == 0):
			temp = self.start_mine(grid, grid_visited, i, j - 1)
			max_choice = max(temp, max_choice)
		if j + 1 < len(grid[0]) and grid[i][j + 1] != 0 and (grid_visited[i][j + 1] == 0):
			temp = self.start_mine(grid, grid_visited, i, j + 1)
			max_choice = max(temp, max_choice)
		grid_visited[i][j] = 0
		return total + max_choice


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.ret = 0
		self.grid = grid
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					self.dfs(i, j, 0)
		return self.ret

	def dfs(self, i, j, cur_gold):
		self.ret = max(self.ret, cur_gold)
		if (0 <= i < len(self.grid) and 0 <= j < len(self.grid[0])) and self.grid[i][j] != 0:
			gold = self.grid[i][j]
			for (m, n) in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
				self.grid[i][j] = 0
				self.dfs(i + m, j + n, cur_gold + gold)
				self.grid[i][j] = gold


class Solution:

	def __init__(self):
		self.moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		best = 0
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if self.canMove(i, j, grid, set()):
					total = self.moveNext(i, j, grid, set(), 0)
					best = max(best, total)
		return best

	def moveNext(self, x, y, grid, visited, total):
		visited.add((x, y))
		total = total + grid[x][y]
		best = total
		for move in self.moves:
			if self.canMove(x + move[0], y + move[1], grid, visited):
				s = self.moveNext(x + move[0], y + move[1], grid, visited.copy(), total)
				if s > best:
					best = s
		return best

	def canMove(self, x, y, grid, visited):
		return (x >= 0 and x < len(grid)) and (y >= 0 and y < len(grid[0])) and (grid[x][y] != 0) and ((x, y) not in visited)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i, j, gold_so_far):
			self.max_gold = max(self.max_gold, gold_so_far)
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] != 0):
				gold_amt = grid[i][j]
				grid[i][j] = 0
				neigbors = [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]
				for (x, y) in neigbors:
					dfs(x, y, gold_so_far + gold_amt)
				grid[i][j] = gold_amt
		self.max_gold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					dfs(i, j, 0)
		return self.max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def sorround(curr):
			posts = [[1, 0], [0, 1], [-1, 0], [0, -1]]
			for i in posts:
				ii = i[0] + curr[0]
				jj = i[1] + curr[1]
				if ii < len(grid) and ii >= 0 and (jj >= 0) and (jj < len(grid[0])) and (grid[ii][jj] != 0):
					yield (ii, jj)

		def depth_first_search(cur):
			cur_sum = grid[cur[0]][cur[1]]
			ans = 0
			for i in sorround(cur):
				if i not in visited or visited[i] == False:
					visited[i] = True
					mx = depth_first_search(i)
					ans = max(ans, mx)
					visited[i] = False
			return cur_sum + ans
		cans = 0
		visited = {}
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					visited[i, j] = True
					cs = depth_first_search((i, j))
					cans = max(cs, cans)
					visited[i, j] = False
		return cans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if len(grid) == 0 or len(grid[0]) == 0:
			return 0

		def collectGold(r, c, goldSoFar):
			pts = [[0, 1], [1, 0], [-1, 0], [0, -1]]
			maxGold = goldSoFar
			for p in pts:
				nR = p[0] + r
				nC = p[1] + c
				if 0 <= nR < len(grid) and 0 <= nC < len(grid[0]) and (grid[nR][nC] != 0):
					v = grid[nR][nC]
					grid[nR][nC] = 0
					gold = collectGold(nR, nC, goldSoFar + v)
					maxGold = max(gold, maxGold)
					grid[nR][nC] = v
			return maxGold
		maxGold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					v = grid[i][j]
					grid[i][j] = 0
					gold = collectGold(i, j, v)
					maxGold = max(maxGold, gold)
					grid[i][j] = v
		return maxGold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		visited = set()

		def dfs(i, j, sum):
			if i < 0 or i == m or j < 0 or (j == n) or ((i, j) in visited) or (grid[i][j] == 0):
				return sum
			visited.add((i, j))
			maxi = 0
			for (x, y) in [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]:
				maxi = max(maxi, dfs(x, y, sum + grid[i][j]))
			visited.remove((i, j))
			return maxi
		return max((dfs(i, j, 0) for i in range(m) for j in range(n) if grid[i][j] != 0))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		self.maxgold = 0

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

		def backtrack(cell, gold, visited):
			self.maxgold = max(self.maxgold, gold)
			(x, y) = (cell[0], cell[1])
			neighbours = [[x - 1, y], [x + 1, y], [x, y + 1], [x, y - 1]]
			for nbr in neighbours:
				if isvalid(nbr[0], nbr[1]) and (not visited[nbr[0]][nbr[1]]) and (grid[nbr[0]][nbr[1]] != 0):
					visited[nbr[0]][nbr[1]] = True
					gold += grid[nbr[0]][nbr[1]]
					backtrack(nbr, gold, visited)
					self.maxgold = max(self.maxgold, gold)
					gold -= grid[nbr[0]][nbr[1]]
					visited[nbr[0]][nbr[1]] = False
		visited = [[False] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					visited[i][j] = True
					backtrack([i, j], grid[i][j], visited)
					visited[i][j] = False
		return self.maxgold


class Solution:

	def is_valid(self, grid, i, j):
		valid_i = 0 <= i <= len(grid) - 1
		valid_j = 0 <= j <= len(grid[0]) - 1
		if not valid_i or not valid_j:
			return False
		if grid[i][j] == 0:
			return False
		return True

	def find_path(self, grid, i, j, gold, visited, max_gold):
		visited.add((i, j))
		gold += grid[i][j]
		max_gold[0] = max(gold, max_gold[0])
		for (x_, y_) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			if self.is_valid(grid, i + x_, j + y_) and (not (i + x_, j + y_) in visited):
				self.find_path(grid, i + x_, j + y_, gold, visited, max_gold)
		visited.remove((i, j))

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_gold = [float('-inf')]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					self.find_path(grid, i, j, 0, set(), max_gold)
		return max_gold[0] if max_gold != float('-inf') else 0


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0

		def dfs(i, j, gold, visited):
			nonlocal ans
			if i < 0 or i >= rows or j < 0 or (j >= cols) or ((i, j) in visited) or (grid[i][j] == 0):
				ans = max(ans, gold)
				return
			visited.add((i, j))
			for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				dfs(i + di, j + dj, gold + grid[i][j], visited)
			visited.remove((i, j))
		(ans, rows, cols) = (0, len(grid), len(grid[0]))
		for row in range(rows):
			for col in range(cols):
				dfs(row, col, 0, set())
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(nrow, ncol) = (len(grid), len(grid[0]))
		possible_starts = [(i, j) for i in range(nrow) for j in range(ncol) if grid[i][j] != 0]
		max_gold = 0
		for start in possible_starts:
			path_stack = [start]
			cell_to_other_paths = collections.defaultdict(list)
			(x, y) = start
			cumulated_gold = grid[x][y]
			while path_stack:
				found_next = False
				if x - 1 >= 0 and grid[x - 1][y] != 0 and ((x - 1, y) not in path_stack):
					found_next = True
					(tmp_x, tmp_y) = (x - 1, y)
				if x + 1 < nrow and grid[x + 1][y] != 0 and ((x + 1, y) not in path_stack):
					if found_next:
						cell_to_other_paths[x, y].append((x + 1, y))
					else:
						found_next = True
						(tmp_x, tmp_y) = (x + 1, y)
				if y - 1 >= 0 and grid[x][y - 1] != 0 and ((x, y - 1) not in path_stack):
					if found_next:
						cell_to_other_paths[x, y].append((x, y - 1))
					else:
						found_next = True
						(tmp_x, tmp_y) = (x, y - 1)
				if y + 1 < ncol and grid[x][y + 1] != 0 and ((x, y + 1) not in path_stack):
					if found_next:
						cell_to_other_paths[x, y].append((x, y + 1))
					else:
						found_next = True
						(tmp_x, tmp_y) = (x, y + 1)
				if found_next:
					path_stack.append((tmp_x, tmp_y))
					cumulated_gold += grid[tmp_x][tmp_y]
					(x, y) = (tmp_x, tmp_y)
				else:
					max_gold = max(max_gold, cumulated_gold)
					while path_stack and len(cell_to_other_paths.get(path_stack[-1], [])) == 0:
						(pop_x, pop_y) = path_stack.pop(-1)
						cumulated_gold -= grid[pop_x][pop_y]
					if not path_stack:
						break
					(x, y) = cell_to_other_paths[path_stack[-1]].pop(0)
					path_stack.append((x, y))
					cumulated_gold += grid[x][y]
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		visited = set()
		max_path = [0]
		row_len = len(grid)
		col_len = len(grid[0])

		def gold_finder(cur_row, cur_col, visited, path_so_far):
			if cur_row < 0 or cur_row >= row_len or cur_col < 0 or (cur_col >= col_len) or (grid[cur_row][cur_col] == 0):
				max_path[0] = max(max_path[0], sum(path_so_far))
				return
			if (cur_row, cur_col) in visited:
				return
			visited.add((cur_row, cur_col))
			gold_finder(cur_row + 1, cur_col, visited, path_so_far + [grid[cur_row][cur_col]])
			gold_finder(cur_row - 1, cur_col, visited, path_so_far + [grid[cur_row][cur_col]])
			gold_finder(cur_row, cur_col + 1, visited, path_so_far + [grid[cur_row][cur_col]])
			gold_finder(cur_row, cur_col - 1, visited, path_so_far + [grid[cur_row][cur_col]])
			visited.remove((cur_row, cur_col))
			return
		for row in range(row_len):
			for col in range(col_len):
				gold_finder(row, col, visited, [])
		return max_path[0]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_total = 0
		num_rows = len(grid)
		num_cols = len(grid[0])
		for i in range(num_rows):
			for j in range(num_cols):
				if grid[i][j] == 0:
					continue
				start_pos = (i, j)
				visited = {(i, j)}
				stack = [(start_pos, visited, grid[i][j])]
				while stack:
					((x, y), visited, running_total) = stack.pop(0)
					neighbors = ((x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y))
					valid_neighbors = [(i, j) for (i, j) in neighbors if 0 <= i < num_rows and 0 <= j < num_cols and (grid[i][j] != 0) and ((i, j) not in visited)]
					if not valid_neighbors:
						if running_total > max_total:
							max_total = running_total
						continue
					else:
						for (x, y) in valid_neighbors:
							copy = visited.copy()
							copy.add((x, y))
							stack.append(((x, y), copy, running_total + grid[x][y]))
		return max_total


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(pos, visited):
			if pos in visited or grid[pos[0]][pos[1]] == 0:
				return 0
			next_visited = visited | set([pos])
			next_pos = [(pos[0] - 1, pos[1]), (pos[0] + 1, pos[1]), (pos[0], pos[1] - 1), (pos[0], pos[1] + 1)]
			max_child = 0
			for p in next_pos:
				if -1 < p[0] < n and -1 < p[1] < m:
					max_child = max(max_child, dfs(p, next_visited))
			return grid[pos[0]][pos[1]] + max_child
		n = len(grid)
		m = len(grid[0])
		max_gold = 0
		for i in range(n):
			for j in range(m):
				max_gold = max(max_gold, dfs((i, j), set()))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		self.maxgold = 0

		def isValid(i, j):
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] != 0):
				return True
			else:
				return False

		def helper(i, j, cursum):
			for direction in directions:
				new_i = i + direction[0]
				new_j = j + direction[1]
				if isValid(new_i, new_j):
					gold = grid[new_i][new_j]
					grid[new_i][new_j] = 0
					helper(new_i, new_j, cursum + gold)
					grid[new_i][new_j] = gold
			self.maxgold = max(self.maxgold, cursum)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					gold = grid[i][j]
					grid[i][j] = 0
					helper(i, j, gold)
					grid[i][j] = gold
		return self.maxgold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		i_len = len(grid)
		j_len = len(grid[0])
		max_shit = 0

		def moves(i, j, amount):
			nonlocal max_shit, i_len, j_len
			if i < 0 or j < 0 or i == i_len or (j == j_len) or (grid[i][j] == 0):
				if amount > max_shit:
					max_shit = amount
				return
			amount += grid[i][j]
			tmp = grid[i][j]
			grid[i][j] = 0
			moves(i + 1, j, amount)
			moves(i - 1, j, amount)
			moves(i, j + 1, amount)
			moves(i, j - 1, amount)
			grid[i][j] = tmp
		for i in range(i_len):
			for j in range(j_len):
				if grid[i][j] != 0:
					moves(i, j, 0)
		return max_shit


class Solution:

	def __init__(self):
		self.moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]

	def dfs(self, r, c):
		if r < 0 or r == self.m or c < 0 or (c == self.n) or (self.grid[r][c] == 0):
			return 0
		original = self.grid[r][c]
		self.grid[r][c] = 0
		maxGold = max((self.dfs(r + x, c + y) for (x, y) in self.moves))
		self.grid[r][c] = original
		return maxGold + original

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.m = len(grid)
		self.n = len(grid[0])
		self.grid = grid
		return max((self.dfs(i, j) for i in range(self.m) for j in range(self.n)))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		d = []
		m = len(grid)
		n = len(grid[0])
		gold = []
		for i in range(m):
			for j in range(n):
				if grid[i][j] > 0:
					gold.append((i, j))
		d = [[1, 0], [-1, 0], [0, 1], [0, -1]]

		def dfs(x, y, seen):
			if (x, y) in seen or x < 0 or x >= m or (y < 0) or (y >= n) or (grid[x][y] <= 0):
				return 0
			a = seen.copy()
			a.add((x, y))
			return grid[x][y] + max((dfs(x + dx, y + dy, a) for (dx, dy) in d))
		return max((dfs(x, y, set()) for (x, y) in gold))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i: int, j: int, sum_so_far: int, seen: set) -> int:
			if i < 0 or i >= m or j < 0 or (j >= n) or (not grid[i][j]) or ((i, j) in seen):
				return sum_so_far
			seen.add((i, j))
			sum_so_far += grid[i][j]
			mx = 0
			for (x, y) in ((i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)):
				mx = max(dfs(x, y, sum_so_far, seen), mx)
			seen.discard((i, j))
			return mx
		(m, n) = (len(grid), len(grid[0]))
		all_gold_path = 0
		for row in range(m):
			for col in range(n):
				all_gold_path = max(all_gold_path, dfs(row, col, 0, set()))
		return all_gold_path

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		visited = set()
		max_path = [0]
		row_len = len(grid)
		col_len = len(grid[0])

		def gold_finder(cur_row, cur_col, visited, path_so_far):
			if cur_row < 0 or cur_row >= row_len or cur_col < 0 or (cur_col >= col_len) or (grid[cur_row][cur_col] == 0):
				max_path[0] = max(max_path[0], sum(path_so_far))
				return
			if (cur_row, cur_col) in visited:
				return
			visited.add((cur_row, cur_col))
			gold_finder(cur_row + 1, cur_col, visited, path_so_far + [grid[cur_row][cur_col]])
			gold_finder(cur_row - 1, cur_col, visited, path_so_far + [grid[cur_row][cur_col]])
			gold_finder(cur_row, cur_col + 1, visited, path_so_far + [grid[cur_row][cur_col]])
			gold_finder(cur_row, cur_col - 1, visited, path_so_far + [grid[cur_row][cur_col]])
			visited.remove((cur_row, cur_col))
			return
		for row in range(row_len):
			for col in range(col_len):
				gold_finder(row, col, visited, [])
		return max_path[0]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		x = [0, 1, 0, -1]
		y = [1, 0, -1, 0]
		(m, n) = (len(grid), len(grid[0]))
		ans = -math.inf
		visited = [[False for _ in range(n)] for _ in range(m)]

		def helper(cur, total):
			(curX, curY) = cur
			total += grid[curX][curY]
			visited[curX][curY] = True
			nonlocal ans
			ans = max(ans, total)
			for (dx, dy) in zip(x, y):
				(candX, candY) = (curX + dx, curY + dy)
				if 0 <= candX < m and 0 <= candY < n and grid[candX][candY] and (not visited[candX][candY]):
					print(candX, candY)
					helper([candX, candY], total)
			visited[curX][curY] = False
		for r in range(m):
			for c in range(n):
				if grid[r][c]:
					helper([r, c], 0)
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.res = 0
		(m, n) = (len(grid), len(grid[0]))

		def dfs(x, y, visited, cnt):
			if any((0 <= nx < m and 0 <= ny < n and (grid[nx][ny] != 0) and ((nx, ny) not in visited) for (nx, ny) in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]])):
				for (nx, ny) in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
					if 0 <= nx < m and 0 <= ny < n and (grid[nx][ny] != 0) and ((nx, ny) not in visited):
						dfs(nx, ny, visited | {(nx, ny)}, cnt + grid[nx][ny])
			else:
				self.res = max(self.res, cnt)
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					dfs(i, j, {(i, j)}, grid[i][j])
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(i, j, total):
			if i < 0 or j < 0 or i >= m or (j >= n) or (grid[i][j] == 0) or (grid[i][j] > 100):
				return total
			total += grid[i][j]
			grid[i][j] += 1000
			temp_max = 0
			for (x, y) in ((i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)):
				temp_max = max(dfs(x, y, total), temp_max)
			grid[i][j] -= 1000
			return temp_max
		m = len(grid)
		n = len(grid[0])
		return max((dfs(i, j, 0) for i in range(m) for j in range(n)))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		results = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 0:
					continue
				tmp = grid[i][j]
				grid[i][j] = '*'
				self.helper([tmp], i, j, grid, results)
				grid[i][j] = tmp
		maxV = -sys.maxsize
		for i in results:
			if sum(i) > maxV:
				maxV = sum(i)
		return maxV

	def helper(self, sub, ii, jj, grid, results):
		if sub[-1] == 0:
			results.append(sub.copy())
			return
		ll = [[ii - 1, jj], [ii + 1, jj], [ii, jj - 1], [ii, jj + 1]]
		for l in ll:
			if l[0] < 0 or l[0] > len(grid) - 1:
				continue
			if l[1] < 0 or l[1] > len(grid[0]) - 1:
				continue
			if grid[l[0]][l[1]] == '*':
				continue
			sub.append(grid[l[0]][l[1]])
			tmp = grid[l[0]][l[1]]
			grid[l[0]][l[1]] = '*'
			self.helper(sub, l[0], l[1], grid, results)
			grid[l[0]][l[1]] = tmp
			sub.pop()


def isValid(i, j, n, m):
	return i >= 0 and j >= 0 and (i < n) and (j < m)

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		(n, m) = (len(grid), len(grid[0]))

		def dfs(i, j, curr_sum, visited):
			if not isValid(i, j, n, m) or (i, j) in visited or (not grid[i][j]):
				return curr_sum
			curr_sum += grid[i][j]
			final = 0
			visited.add((i, j))
			for (x, y) in directions:
				(newX, newY) = (i + x, j + y)
				final = max(dfs(newX, newY, curr_sum, visited), final)
			visited.remove((i, j))
			return final
		ans = 0
		visited = set()
		for r in range(n):
			for c in range(m):
				ans = max(ans, dfs(r, c, 0, visited))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		ROWS = len(grid)
		COLS = len(grid[0])
		self.mx = 0
		seen = set()

		def dfs(r, c):
			if not 0 <= r < ROWS or not 0 <= c < COLS or (r, c) in seen or (grid[r][c] == 0):
				return 0
			val = grid[r][c]
			seen.add((r, c))
			mx = max(dfs(r + 1, c), dfs(r - 1, c), dfs(r, c + 1), dfs(r, c - 1))
			seen.remove((r, c))
			return val + mx
		for r in range(ROWS):
			for c in range(COLS):
				if grid[r][c] != 0:
					self.mx = max(self.mx, dfs(r, c))
		return self.mx


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		ans = 0

		def bfs(a, s, d, f):
			nonlocal ans
			q = collections.deque([(a, s, d, f)])
			while q:
				(j, k, tot, seen) = q.popleft()
				for (m, n) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
					(jm, kn) = (j + m, k + n)
					if jm > -1 and kn > -1 and (jm < len(grid)) and (kn < len(grid[0])) and grid[jm][kn] and ((jm, kn) not in seen):
						q.append((jm, kn, tot + grid[jm][kn], seen | {(jm, kn)}))
					else:
						ans = max(ans, tot)
		for i in range(len(grid)):
			for x in range(len(grid[0])):
				if grid[i][x]:
					bfs(i, x, grid[i][x], {(i, x)})
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def bfs(i, j, path):
			if i < 0 or i >= m or j < 0 or (j >= n) or (grid[i][j] == 0) or ((i, j) in path):
				return 0
			return grid[i][j] + max([bfs(i - 1, j, path + [(i, j)]), bfs(i + 1, j, path + [(i, j)]), bfs(i, j - 1, path + [(i, j)]), bfs(i, j + 1, path + [(i, j)])])
		maxval = None
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					path = []
					val = bfs(i, j, path)
					if maxval is None or val > maxval:
						maxval = val
		return maxval


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def neighbor(r, c):
			for (dr, dc) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
				if 0 <= dr < nrow and 0 <= dc < ncol:
					yield (dr, dc)
		self.cur_gold = 0
		self.max_gold = 0

		def backtrack(r, c):
			if grid[r][c] == 0:
				return
			gold_cnt = grid[r][c]
			self.cur_gold += gold_cnt
			self.max_gold = max(self.max_gold, self.cur_gold)
			grid[r][c] = 0
			for (dr, dc) in neighbor(r, c):
				backtrack(dr, dc)
			grid[r][c] = gold_cnt
			self.cur_gold -= gold_cnt
		(nrow, ncol) = (len(grid), len(grid[0]))
		for r in range(nrow):
			for c in range(ncol):
				backtrack(r, c)
		return self.max_gold


class Solution:

	def dfs(self, i, j, gold, grid, m, n):
		if 0 <= i < m and 0 <= j < n:
			if grid[i][j] != 0:
				temp = grid[i][j]
				grid[i][j] = 0
				gold = max((self.dfs(x, y, gold + temp, grid, m, n) for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))))
				grid[i][j] = temp
		return gold

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		res = []
		for i in range(m):
			for j in range(n):
				res.append(self.dfs(i, j, 0, grid, m, n))
		return max(res)


class Solution:
	DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(N, M) = (len(grid), len(grid[0]))
		self.res = 0

		def dfs(x: int, y: int, v: int, done: set):
			self.res = max(self.res, v)
			for (dx, dy) in self.DIRS:
				(xx, yy) = (x + dx, y + dy)
				if not 0 <= xx < N or not 0 <= yy < M or (xx, yy) in done or (grid[xx][yy] == 0):
					continue
				done.add((xx, yy))
				dfs(xx, yy, v + grid[xx][yy], done)
				done.remove((xx, yy))
		done = set()
		for ii in range(N):
			for jj in range(M):
				zero_num = [idx for (idx, (dx, dy)) in enumerate(self.DIRS) if 0 <= ii + dx < N and 0 <= jj + dy < M and grid[ii + dx][jj + dy]]
				flag = len(zero_num) <= 1 or (len(zero_num) == 2 and 1 in zero_num and (2 in zero_num))
				if grid[ii][jj] and flag:
					done.add((ii, jj))
					dfs(ii, jj, grid[ii][jj], done)
					done.remove((ii, jj))
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def dfs(r, c, total, vis):
			nonlocal maxx
			if r < 0 or r >= m or c < 0 or (c >= n) or (grid[r][c] == 0) or ((r, c) in vis):
				return
			total += grid[r][c]
			maxx = max(total, maxx)
			dfs(r + 1, c, total, vis + [(r, c)])
			dfs(r - 1, c, total, vis + [(r, c)])
			dfs(r, c + 1, total, vis + [(r, c)])
			dfs(r, c - 1, total, vis + [(r, c)])
		grt = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					maxx = 0
					dfs(i, j, 0, [])
					grt = max(grt, maxx)
		return grt


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		(r, c) = (len(grid), len(grid[0]))

		def dfs(i, j, curr, visited):
			self.mx = max(self.mx, curr)
			for (di, dj) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				if 0 <= i + di < r and 0 <= j + dj < c and (grid[i + di][j + dj] != 0) and ((i + di, j + dj) not in visited):
					visited.add((i + di, j + dj))
					dfs(i + di, j + dj, curr + grid[i + di][j + dj], visited)
					visited.remove((i + di, j + dj))
			return
		self.mx = 0
		for i in range(r):
			for j in range(c):
				if grid[i][j] != 0:
					dfs(i, j, grid[i][j], {(i, j)})
		return self.mx


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])

		def dfs(i, j, total, visited):
			if i < 0 or i >= n or j < 0 or (j >= m) or (grid[i][j] == 0) or ((i, j) in visited):
				return
			nonlocal ma
			total = total + grid[i][j]
			ma = max(ma, total)
			dfs(i + 1, j, total, visited + [(i, j)])
			dfs(i - 1, j, total, visited + [(i, j)])
			dfs(i, j + 1, total, visited + [(i, j)])
			dfs(i, j - 1, total, visited + [(i, j)])
		c = -1
		for i in range(n):
			for j in range(m):
				if grid[i][j] != 0:
					ma = 0
					dfs(i, j, 0, [])
					c = max(c, ma)
		return c


hops = [[-1, 0], [1, 0], [0, 1], [0, -1]]

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		g = 0
		path = set()
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				temp = self.goldHelper(grid, r, c, path)
				g = max(g, temp)
		return g

	def goldHelper(self, grid: List[List[int]], r, c, path):
		if (r, c) in path:
			return 0
		if r < 0 or r >= len(grid):
			return 0
		if c < 0 or c >= len(grid[0]):
			return 0
		if grid[r][c] == 0:
			return 0
		path.add((r, c))
		curr = 0
		for (v, a) in hops:
			curr = max(curr, self.goldHelper(grid, r + v, c + a, path))
		path.remove((r, c))
		return curr + grid[r][c]


class Solution:

	def __init__(self):
		self.max_len = 0

	def isValid(self, r, c, grid):
		if r < 0 or c < 0 or r >= self.M or (c >= self.N) or (grid[r][c] == 0):
			return False
		return True

	def dfs(self, r, c, visited, path_sum, grid):
		if (r, c) in visited or not self.isValid(r, c, grid):
			return
		visited.add((r, c))
		path_sum = path_sum + grid[r][c]
		self.max_len = max(self.max_len, path_sum)
		self.dfs(r + 1, c, set(visited), path_sum, grid)
		self.dfs(r - 1, c, set(visited), path_sum, grid)
		self.dfs(r, c + 1, set(visited), path_sum, grid)
		self.dfs(r, c - 1, set(visited), path_sum, grid)

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(self.M, self.N) = (len(grid), len(grid[0]))
		for m in range(self.M):
			for n in range(self.N):
				self.dfs(m, n, set(), 0, grid)
		return self.max_len


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(self.grid, self.lr, self.lc) = (grid, len(grid), len(grid[0]) if grid else 0)
		return max((self.helper(i, j) for i in range(self.lr) for j in range(self.lc) if grid[i][j])) if grid else 0

	def helper(self, x, y):
		nei = [(i, j) for (i, j) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)) if i in range(self.lr) and j in range(self.lc) and self.grid[i][j]]
		(res, val, self.grid[x][y]) = (self.grid[x][y], self.grid[x][y], 0)
		for n in nei:
			res = max(res, self.helper(*n) + val)
		self.grid[x][y] = val
		return res


class Solution:

	def get_sum(self, grid, x, y, sum_, all_grids):
		if [x, y] not in all_grids and (not grid[x][y] == 0):
			sum_ = sum_ + grid[x][y]
			all_grids.append([x, y])
			(sum_top, sum_bottom, sum_left, sum_right) = (sum_, sum_, sum_, sum_)
			if x > 0:
				sum_top = self.get_sum(grid, x - 1, y, sum_, all_grids.copy())
			if x < len(grid) - 1:
				sum_bottom = self.get_sum(grid, x + 1, y, sum_, all_grids.copy())
			if y > 0:
				sum_left = self.get_sum(grid, x, y - 1, sum_, all_grids.copy())
			if y < len(grid[0]) - 1:
				sum_right = self.get_sum(grid, x, y + 1, sum_, all_grids.copy())
			return max(sum_top, sum_bottom, sum_left, sum_right)
		else:
			return sum_

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		sums = []
		for m in range(len(grid)):
			for n in range(len(grid[m])):
				sums.append(self.get_sum(grid, m, n, 0, []))
		return max(sums)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		csum = msum = 0

		def backtrack(r, c):
			direct = [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]
			nonlocal msum, csum
			isbool = True
			for (p, q) in direct:
				if 0 <= p < m and 0 <= q < n and (0 < grid[p][q]):
					isbool = False
					value = grid[p][q]
					csum += grid[p][q]
					grid[p][q] = 0
					backtrack(p, q)
					grid[p][q] = value
					csum -= value
			if isbool:
				msum = max(msum, csum)
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					csum = value = grid[i][j]
					grid[i][j] = 0
					backtrack(i, j)
					grid[i][j] = value
		return msum


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def q(g, i, j, t, s, vis):
			if i >= len(g) or j >= len(g[0]) or i < 0 or (j < 0) or (g[i][j] == 0) or (vis[i][j] == 1):
				s[0] = max(s[0], t[0])
				return
			temp = g[i][j]
			g[i][j] = 0
			t[0] += temp
			q(g, i, j + 1, t, s, vis)
			q(g, i + 1, j, t, s, vis)
			q(g, i - 1, j, t, s, vis)
			q(g, i, j - 1, t, s, vis)
			t[0] -= temp
			g[i][j] = temp
		s = [0]
		t = [0]
		vis = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				t = [0]
				q(grid, i, j, t, s, vis)
		return s[0]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(seen, n, m) = ({}, len(grid), len(grid[0]))
		(maxy, x, y) = (0, [1, -1, 0, 0], [0, 0, -1, 1])
		dp = [[0] * m for _ in range(n)]

		def path(i, j, d):
			mm = d
			for k in range(len(x)):
				(r, c) = (i + x[k], j + y[k])
				if 0 <= r < n and 0 <= c < m and (grid[r][c] != 0):
					if (r, c) not in seen or not seen[r, c]:
						seen[r, c] = True
						mm = max(mm, path(r, c, d + grid[r][c]))
						seen[r, c] = False
			return mm
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 0:
					continue
				seen[i, j] = True
				maxy = max(maxy, path(i, j, grid[i][j]))
				seen[i, j] = False
		return maxy


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		ans = [0]

		def path(i, j, seen, val):
			ans[0] = max(ans[0], val)
			adjacent = [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]
			for (k, l) in adjacent:
				if k < 0 or k >= m or l < 0 or (l >= n):
					continue
				if grid[k][l] != 0 and (k, l) not in seen:
					path(k, l, seen + [(k, l)], val + grid[k][l])
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					path(i, j, [(i, j)], grid[i][j])
		return max(ans)


class Solution:

	def getMaxGoldHelper(self, visited, grid, curx, cury):
		if (curx, cury) in visited:
			return 0
		visited.add((curx, cury))
		ret = grid[cury][curx]
		max_recur = 0
		for (nextx, nexty) in [(curx - 1, cury), (curx + 1, cury), (curx, cury - 1), (curx, cury + 1)]:
			if nextx < 0 or nextx >= len(grid[0]) or nexty < 0 or (nexty >= len(grid)):
				continue
			if grid[nexty][nextx] > 0:
				max_recur = max(max_recur, self.getMaxGoldHelper(visited, grid, nextx, nexty))
		visited.remove((curx, cury))
		return ret + max_recur

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_seen = 0
		for row in range(len(grid)):
			for col in range(len(grid[row])):
				max_seen = max(max_seen, self.getMaxGoldHelper(set(), grid, col, row))
		return max_seen


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.nums = grid.copy()
		self.results = []
		self.visited = [[False for i in range(len(grid[0]))] for i in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					maxVal = self.getTheGold(i, j, 0)
		return max(self.results)

	def getTheGold(self, i, j, value):
		if self.isSafe(i, j):
			self.visited[i][j] = True
			self.getTheGold(i + 1, j, value + self.nums[i][j])
			self.getTheGold(i, j + 1, value + self.nums[i][j])
			self.getTheGold(i - 1, j, value + self.nums[i][j])
			self.getTheGold(i, j - 1, value + self.nums[i][j])
			self.visited[i][j] = False
		else:
			return self.results.append(value)

	def isSafe(self, i, j):
		if i >= 0 and i < len(self.nums) and (j >= 0) and (j < len(self.nums[0])):
			return self.nums[i][j] != 0 and self.visited[i][j] == False
		return False


class Solution:

	def __init__(self):
		self.EMPTY = 0
		self.DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		max_gold = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == self.EMPTY:
					continue
				max_gold = max(max_gold, self.dfs(grid, i, j, set()))
		return max_gold

	def dfs(self, grid, x, y, visited):
		if not self.inbound(grid, x, y) or (x, y) in visited or grid[x][y] == self.EMPTY:
			return 0
		visited.add((x, y))
		gold = 0
		for (delta_x, delta_y) in self.DIR:
			(next_x, next_y) = (x + delta_x, y + delta_y)
			gold = max(gold, self.dfs(grid, next_x, next_y, visited))
		gold += grid[x][y]
		visited.discard((x, y))
		return gold

	def inbound(self, grid, x, y):
		return 0 <= x < len(grid) and 0 <= y < len(grid[0])


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		return max([self.helper(grid, row, col) for row in range(len(grid)) for col in range(len(grid[row]))])

	def helper(self, grid, row, col):
		if not self.are_valid_coordinates(grid, row, col):
			return 0
		curr_gold = grid[row][col]
		grid[row][col] = -1
		all_results = [curr_gold] + [curr_gold + self.helper(grid, nrow, ncol) for (nrow, ncol) in self.get_neighbors(row, col)]
		grid[row][col] = curr_gold
		return max(all_results)

	def are_valid_coordinates(self, grid, row, col):
		return row >= 0 and col >= 0 and (row < len(grid)) and (col < len(grid[row])) and (grid[row][col] > 0)

	def get_neighbors(self, row, col):
		return [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(nr, nc) = (len(grid), len(grid[0]))
		delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]

		def dfs(i, j):
			(gold, grid[i][j]) = (grid[i][j], 0)
			max_gold = 0
			for (dx, dy) in delta:
				(x, y) = (i + dx, j + dy)
				if 0 <= x < nr and 0 <= y < nc and (grid[x][y] > 0):
					max_gold = max(max_gold, dfs(x, y))
			grid[i][j] = gold
			return max_gold + gold
		return max((dfs(i, j) for i in range(nr) for j in range(nc) if grid[i][j] > 0))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def helper(r, c, total, visited):
			if r >= len(grid) or c >= len(grid[0]) or r < 0 or (c < 0) or (grid[r][c] == 0) or ((r, c) in visited):
				return
			total += grid[r][c]
			self.maxGold = max(self.maxGold, total)
			helper(r + 1, c, total, visited + [(r, c)])
			helper(r - 1, c, total, visited + [(r, c)])
			helper(r, c + 1, total, visited + [(r, c)])
			helper(r, c - 1, total, visited + [(r, c)])
		gg = 0
		self.maxGold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					helper(i, j, 0, [])
					gg = max(gg, self.maxGold)
					self.maxGold = 0
		return gg


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		num_rows = len(grid)
		num_cols = len(grid[0])
		deltas = ((-1, 0), (1, 0), (0, -1), (0, 1))

		def explore(y: int, x: int, score=0, visited=None) -> int:
			if not visited:
				visited = set()
			if y < 0 or y >= num_rows or x < 0 or (x >= num_cols):
				return score
			if grid[y][x] == 0 or (y, x) in visited:
				return score
			score += grid[y][x]
			visited = set([*visited, (y, x)])
			best = score
			for (dy, dx) in deltas:
				best = max(best, explore(y + dy, x + dx, score, visited))
			return best
		best = 0
		for y in range(num_rows):
			for x in range(num_cols):
				best = max(best, explore(y, x))
		return best


class Solution:

	def getMaximumGold(self, g: List[List[int]]) -> int:

		def dfs(i, j, visited):
			if not (0 <= i < len(g) and 0 <= j < len(g[0]) and (g[i][j] != 0) and ((i, j) not in visited)):
				return 0
			visited.add((i, j))
			res = g[i][j] + max(0, max((dfs(i + x, j + y, visited) for (x, y) in [[-1, 0], [1, 0], [0, 1], [0, -1]])))
			visited.remove((i, j))
			return res
		return max((dfs(i, j, set()) for i in range(len(g)) for j in range(len(g[0]))))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		res = 0
		summ = 0
		visited = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if self.in_area(grid, i, j):
					value = self.dfs(grid, i, j, summ, visited)
					res = max(res, value)
		return res

	def dfs(self, grid, r, c, summ, visited):
		if not self.in_area(grid, r, c):
			return summ
		if not grid[r][c] or (r, c) in visited:
			return summ
		visited.add((r, c))
		summ += grid[r][c]
		res = 0
		moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		for (dr, dc) in moves:
			r2 = r + dr
			c2 = c + dc
			value = self.dfs(grid, r2, c2, summ, visited)
			res = max(res, value)
		visited.discard((r, c))
		return res

	def in_area(self, grid, r, c):
		return 0 <= r < len(grid) and 0 <= c < len(grid[0])


class Solution:

	def __init__(self):
		self.m = 0
		self.n = 0
		self.grid = None

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not len(grid):
			return 0
		self.grid = grid
		self.m = len(grid)
		self.n = len(grid[0])
		ans = 0
		for i in range(self.m):
			for j in range(self.n):
				ans = max(ans, self.dfs(i, j))
		return ans

	def dfs(self, x, y):
		res = 0
		amt = self.grid[x][y]
		self.grid[x][y] = 0
		directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		for (dx, dy) in directions:
			i = x + dx
			j = y + dy
			if i >= 0 and i < self.m and (j >= 0) and (j < self.n) and (self.grid[i][j] != 0):
				res = max(res, self.grid[i][j] + self.dfs(i, j))
		self.grid[x][y] = amt
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		res = 0
		M = len(grid)
		N = len(grid[0])
		cords = [[0, 1], [0, -1], [-1, 0], [1, 0]]

		def recur(x, y):
			if x < 0 or x >= M or y < 0 or (y >= N) or (grid[x][y] == 0):
				return 0
			temp = grid[x][y]
			grid[x][y] = 0
			total = 0
			for (dx, dy) in cords:
				dx += x
				dy += y
				total = max(total, recur(dx, dy))
			grid[x][y] = temp
			return total + temp
		for i in range(M):
			for j in range(N):
				if grid[i][j] != 0:
					res = max(recur(i, j), res)
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		path = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		path_indices = [0, 1, 2, 3]

		def value(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n):
				return 0
			return grid[i][j]

		def dfs(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n) or ((i, j) in visited) or (grid[i][j] == 0):
				return 0
			visited.add((i, j))
			golds = [dfs(i + i_, j + j_) for (i_, j_) in path]
			idx = max(path_indices, key=lambda x: golds[x])
			gold = grid[i][j] + golds[idx]
			visited.remove((i, j))
			return gold
		visited = set()
		max_gold = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					gold = dfs(i, j)
					if gold > max_gold:
						max_gold = gold
		return max_gold


import sys

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		rows = len(grid)
		cols = len(grid[0])

		def isValid(start, grid):
			valid = []
			(r, c) = start
			(up, right, left, down) = (True, True, True, True)
			if r == 0:
				up = False
			if r == len(grid) - 1:
				down = False
			if c == 0:
				left = False
			if c == len(grid[0]) - 1:
				right = False
			if down and grid[r + 1][c] != 0:
				valid.append((r + 1, c))
			if up and grid[r - 1][c] != 0:
				valid.append((r - 1, c))
			if right and grid[r][c + 1] != 0:
				valid.append((r, c + 1))
			if left and grid[r][c - 1] != 0:
				valid.append((r, c - 1))
			return valid

		def findMaxPath(maxV, path, start, grid):
			validList = isValid(start, grid)
			if not validList:
				if sum(path) > maxV:
					maxV = sum(path)
			for (r, c) in validList:
				valI = grid[r][c]
				grid[r][c] = 0
				path.append(valI)
				maxV = findMaxPath(maxV, path, (r, c), grid)
				path.pop()
				grid[r][c] = valI
			return maxV
		maxV = -sys.maxsize - 1
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] != 0:
					val = grid[r][c]
					grid[r][c] = 0
					maxV = findMaxPath(maxV, [val], (r, c), grid)
					grid[r][c] = val
		return maxV


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		iMax = len(grid)
		jMax = len(grid[0])
		di = [0, 1, 0, -1]
		dj = [1, 0, -1, 0]
		numOfGold = 0
		goldNumDict = {}
		for i in range(iMax):
			for j in range(jMax):
				if grid[i][j] != 0:
					goldNumDict[i, j] = numOfGold
					numOfGold += 1
		dp = defaultdict(int)

		def findGold(mNow, i0, j0, goldNow):
			subAns = goldNow
			for k in range(4):
				i1 = i0 + di[k]
				j1 = j0 + dj[k]
				if i1 < 0 or j1 < 0 or i1 == iMax or (j1 == jMax) or (grid[i1][j1] == 0) or mNow & 1 << goldNumDict[i1, j1]:
					continue
				subAns = max(subAns, findGold(mNow | 1 << goldNumDict[i1, j1], i1, j1, goldNow + grid[i1][j1]))
			dp[mNow] = max(subAns, dp[mNow])
			return subAns
		ans = 0
		for i in range(iMax):
			for j in range(jMax):
				if grid[i][j] != 0:
					ans = max(ans, findGold(1 << goldNumDict[i, j], i, j, grid[i][j]))
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(R, C) = (len(grid), len(grid[0]))
		O = []

		def check(r, c, Z):
			if -1 < r < R and -1 < c < C and ((r, c) not in Z):
				return True
			return False

		def bt(r, c, res, Z):
			if grid[r][c] == 0:
				O.append(res)
				return
			else:
				a = grid[r][c]
				if check(r + 1, c, Z + [(r, c)]) == True:
					bt(r + 1, c, res + a, Z + [(r, c)])
				if check(r - 1, c, Z + [(r, c)]) == True:
					bt(r - 1, c, res + a, Z + [(r, c)])
				if check(r, c + 1, Z + [(r, c)]) == True:
					bt(r, c + 1, res + a, Z + [(r, c)])
				if check(r, c - 1, Z + [(r, c)]) == True:
					bt(r, c - 1, res + a, Z + [(r, c)])
				return
		for i in range(R):
			for j in range(C):
				if grid[i][j] != 0:
					bt(i, j, 0, [])
		return max(O)


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.max_gold = 0
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				visited = set()
				self.dfs(grid, 0, row, col, visited)
		return self.max_gold

	def dfs(self, grid, curr_gold, i, j, visited):
		if (i, j) in visited or not (i >= 0 and i < len(grid) and (j >= 0) and (j < len(grid[0]))) or grid[i][j] == 0:
			if self.max_gold < curr_gold:
				self.max_gold = curr_gold
			return
		visited.add((i, j))
		self.dfs(grid, curr_gold + grid[i][j], i + 1, j, visited)
		visited.discard((i, j))
		visited.add((i, j))
		self.dfs(grid, curr_gold + grid[i][j], i - 1, j, visited)
		visited.discard((i, j))
		visited.add((i, j))
		self.dfs(grid, curr_gold + grid[i][j], i, j - 1, visited)
		visited.discard((i, j))
		visited.add((i, j))
		self.dfs(grid, curr_gold + grid[i][j], i, j + 1, visited)
		visited.discard((i, j))
		return


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		row = len(grid)
		col = len(grid[0])
		rval = []
		for x in range(row):
			for y in range(col):
				if grid[x][y] == 0:
					continue
				self.traverse(rval, grid, grid[x][y], {(x, y): True}, x, y)
		return max(rval or [0])

	def traverse(self, rval, grid, path, visited, x, y):
		if self.finished(grid, visited, x, y):
			rval.append(path)
			return
		for (new_x, new_y) in [(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]:
			if not self.available(grid, visited, new_x, new_y):
				continue
			visited[x, y] = True
			self.traverse(rval, grid, path + grid[new_x][new_y], visited, new_x, new_y)
			visited[x, y] = False

	def available(self, grid, visited, x, y):
		return 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (grid[x][y] != 0) and (not visited.get((x, y), False))

	def finished(self, grid, visited, x, y):
		for (new_x, new_y) in [(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]:
			if self.available(grid, visited, new_x, new_y):
				return False
		return True


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		ones = set([])
		start = []
		answer = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] != 0:
					ones.add((i, j))
					start.append([(i, j), grid[i][j], set([(i, j)])])
					answer = max(answer, grid[i][j])
		nearby = {}
		for (a, b) in ones:
			nearby[a, b] = []
			for (c, d) in [(a + 1, b), (a - 1, b), (a, b - 1), (a, b + 1)]:
				if (c, d) in ones:
					if a == c and abs(b - d) == 1 or (abs(a - c) == 1 and b == d):
						nearby[a, b].append((c, d))
		while True:
			next = []
			for (a, b, c) in start:
				for a2 in nearby[a]:
					if a2 not in c:
						b2 = b + grid[a2[0]][a2[1]]
						c2 = c.union(set([a2]))
						answer = max(answer, b2)
						next.append([a2, b2, c2])
			start = next
			if len(start) == 0:
				break
		return answer


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def fun(g, i, j):
			if i < 0 or i >= m or j < 0 or (j >= n) or (g[i][j] == 0):
				return 0
			t = g[i][j]
			g[i][j] = 0
			curr = t + max(fun(g, i - 1, j), fun(g, i, j - 1), fun(g, i + 1, j), fun(g, i, j + 1))
			g[i][j] = t
			return curr
		ml = 0
		for i in range(m):
			for j in range(n):
				ml = max(ml, fun(grid, i, j))
		return ml


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		visited = set()
		max_gold = 0

		def dfs(r, c, max_gold):
			if (r, c) in visited or grid[r][c] == 0:
				return max_gold
			visited.add((r, c))
			for (i, j) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
				if 0 <= r + i < len(grid) and 0 <= c + j < len(grid[0]):
					max_gold = max(max_gold, grid[r][c] + dfs(r + i, c + j, 0))
			visited.remove((r, c))
			return max_gold
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] > 0:
					max_gold = max(max_gold, dfs(r, c, 0))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		rows = len(grid)
		cols = len(grid[0])
		self.ans = 0

		def dfs(grid, row, col, currg):
			self.ans = max(self.ans, currg)
			if row >= 0 and row < rows and (col >= 0) and (col < cols) and (grid[row][col] != 0):
				ga = grid[row][col]
				grid[row][col] = 0
				for p in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					dfs(grid, row + p[0], col + p[1], currg + ga)
				grid[row][col] = ga
		for x in range(rows):
			for y in range(cols):
				if grid[x][y] != 0:
					dfs(grid, x, y, 0)
		return self.ans


from collections import defaultdict

class Solution:

	def dfs(self, i, j, m, n, grid):
		tmp = grid[i][j]
		grid[i][j] = 0
		max_next_sum = 0
		for d in {(-1, 0), (1, 0), (0, -1), (0, 1)}:
			(new_i, new_j) = (i + d[0], j + d[1])
			if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j]:
				max_next_sum = max(max_next_sum, self.dfs(new_i, new_j, m, n, grid))
		grid[i][j] = tmp
		return grid[i][j] + max_next_sum

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		res = 0
		if len(grid) < 1 or len(grid[0]) < 1:
			return res
		(m, n) = (len(grid), len(grid[0]))
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					res = max(res, self.dfs(i, j, m, n, grid))
		return res


class Solution:

	def getMaximumGold(self, a: List[List[int]]) -> int:

		def dfs(a, r, c, curSum, res):
			res[0] = max(res[0], curSum)
			temp = a[r][c]
			a[r][c] = -1
			directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
			for d in directions:
				(nr, nc) = (r + d[0], c + d[1])
				if nr >= 0 and nr < len(a) and (nc >= 0) and (nc < len(a[0])):
					if a[nr][nc] > 0:
						dfs(a, nr, nc, curSum + a[nr][nc], res)
			a[r][c] = temp
			return
		res = [0]
		for i in range(0, len(a)):
			for j in range(0, len(a[0])):
				if a[i][j] > 0:
					dfs(a, i, j, a[i][j], res)
		return res[0]


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def getMaxGoldForCoords(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n):
				return 0
			if grid[i][j] == 0:
				return 0
			temp = grid[i][j]
			grid[i][j] = 0
			result = max(getMaxGoldForCoords(i + 1, j), getMaxGoldForCoords(i - 1, j), getMaxGoldForCoords(i, j + 1), getMaxGoldForCoords(i, j - 1)) + temp
			grid[i][j] = temp
			return result
		res = 0
		for i in range(m):
			for j in range(n):
				res = max(res, getMaxGoldForCoords(i, j))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def dfs(x, y):
			if x < 0 or x == m or y < 0 or (y == n) or (grid[x][y] == 0):
				return 0
			val = grid[x][y]
			grid[x][y] = 0
			gain = val + max(dfs(x + 1, y), dfs(x - 1, y), dfs(x, y - 1), dfs(x, y + 1))
			grid[x][y] = val
			return gain
		gold = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					gold = max(gold, dfs(i, j))
		return gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.res = 0
		rows = len(grid)
		cols = len(grid[0])

		def backtrace(i, j, tot):
			self.res = max(self.res, tot + grid[i][j])
			gridVal = grid[i][j]
			grid[i][j] = 0
			for (a, b) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if a >= 0 and b >= 0 and (a < rows) and (b < cols) and (grid[a][b] != 0):
					backtrace(a, b, tot + gridVal)
			grid[i][j] = gridVal
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] != 0:
					backtrace(i, j, 0)
		return self.res


class Solution:

	def getMaximumGold(self, A: List[List[int]]) -> int:

		def dfs(i, j):
			if not (0 <= i < m and 0 <= j < n):
				return (0, set())
			val = A[i][j]
			if val == 0:
				return (0, set())
			A[i][j] = 0
			maxgold = 0
			maxpath = set()
			for (ni, nj) in ((i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)):
				(gold, path) = dfs(ni, nj)
				if gold > maxgold:
					maxgold = gold
					maxpath = path
			A[i][j] = val
			maxpath.add((i, j))
			return (val + maxgold, maxpath)
		maxgold = 0
		maxpath = set()
		(m, n) = (len(A), len(A[0]))
		for i in range(m):
			for j in range(n):
				if (i, j) in maxpath:
					continue
				(gold, path) = dfs(i, j)
				if gold > maxgold:
					maxgold = gold
					maxpath = path
		return maxgold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def dfs(x, y):
			if x < 0 or x >= m or y < 0 or (y >= n) or (grid[x][y] == 0):
				return 0
			t = grid[x][y]
			grid[x][y] = 0
			s = t + max(dfs(x + 1, y), dfs(x - 1, y), dfs(x, y + 1), dfs(x, y - 1))
			grid[x][y] = t
			return s
		res = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					res = max(res, dfs(i, j))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def backtrack(r, c):
			grid[r][c] = -grid[r][c]
			maxlen = 0
			for (i, j) in [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]:
				if 0 <= i < M and 0 <= j < N and (grid[i][j] > 0):
					maxlen = max(maxlen, backtrack(i, j))
			grid[r][c] = -grid[r][c]
			return maxlen + grid[r][c]
		res = 0
		(M, N) = (len(grid), len(grid[0]))
		for r in range(M):
			for c in range(N):
				if grid[r][c] > 0:
					res = max(res, backtrack(r, c))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		max_gold = 0
		(m, n) = (len(grid), len(grid[0]))

		def get_max(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n) or (grid[i][j] == 0):
				return 0
			tmp = grid[i][j]
			max_gold = 0
			grid[i][j] = 0
			max_gold = max(max_gold, get_max(i + 1, j), get_max(i - 1, j), get_max(i, j + 1), get_max(i, j - 1))
			grid[i][j] = tmp
			return max_gold + tmp
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					max_gold = max(max_gold, get_max(i, j))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def dfs(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n) or (grid[i][j] == 0):
				return 0
			gold = grid[i][j]
			grid[i][j] = 0
			total = gold + max(dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1))
			grid[i][j] = gold
			return total
		dp = dict()
		max_gold = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					gold = dfs(i, j)
					max_gold = max(gold, max_gold)
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		m = len(grid)
		n = len(grid[0])

		def get(i, j):
			if i >= 0 and i < m and (j >= 0) and (j < n) and (grid[i][j] != 0):
				gold = grid[i][j]
				grid[i][j] = 0
				maxx = gold + max(get(i + 1, j), get(i - 1, j), get(i, j + 1), get(i, j - 1))
				grid[i][j] = gold
			else:
				maxx = 0
			return maxx
		maxgold = 0
		for i in range(m):
			for j in range(n):
				maxgold = max(maxgold, get(i, j))
		return maxgold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(M, N) = (len(grid), len(grid[0]))
		self.res = 0

		def dfs(grid, i, j, cur):
			nbr = [(i, j + 1), (i, j - 1), (i - 1, j), (i + 1, j)]
			temp = grid[i][j]
			self.res = max(self.res, cur + temp)
			for (r, c) in nbr:
				if 0 <= r < M and 0 <= c < N and grid[r][c]:
					grid[i][j] = 0
					dfs(grid, r, c, cur + temp)
					grid[i][j] = temp
		for i in range(M):
			for j in range(N):
				if grid[i][j]:
					dfs(grid, i, j, 0)
		print(('res = ', self.res))
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def backtrack(r, c):
			if r < 0 or r >= m or c < 0 or (c >= n) or (grid[r][c] == 0):
				return 0
			tmp = grid[r][c]
			grid[r][c] = 0
			val = tmp
			val += max(backtrack(r + 1, c), backtrack(r - 1, c), backtrack(r, c + 1), backtrack(r, c - 1))
			grid[r][c] = tmp
			return val
		ans = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] != 0:
					tmp = backtrack(i, j)
					ans = max(ans, tmp)
		return ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		self.gold = 0

		def DFS(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n):
				return 0
			if grid[i][j] == 0:
				return 0
			tmp = grid[i][j]
			grid[i][j] = 0
			self.gold = max(tmp + DFS(i + 1, j), tmp + DFS(i - 1, j), tmp + DFS(i, j + 1), tmp + DFS(i, j - 1))
			grid[i][j] = tmp
			return self.gold
		res = 0
		for i in range(m):
			for j in range(n):
				self.gold = 0
				res = max(res, DFS(i, j))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		m = len(grid) - 1
		n = len(grid[0]) - 1

		def dfs(i, j, visited):
			val = 0
			visited[i][j] = True
			for co in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				x = i + co[0]
				y = j + co[1]
				if 0 <= x <= m and 0 <= y <= n and (grid[x][y] != 0) and (visited[x][y] == False):
					val = max(val, dfs(x, y, visited))
			visited[i][j] = False
			return val + grid[i][j]
		vis = [[False] * (n + 1) for _ in range(m + 1)]
		res = 0
		for i in range(m + 1):
			for j in range(n + 1):
				if grid[i][j] != 0:
					res = max(res, dfs(i, j, vis))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		nR = len(grid)
		nC = len(grid[0])
		vis = [[0 for i in range(nC)] for j in range(nR)]
		steps = [[0, -1], [-1, 0], [1, 0], [0, 1]]
		_max = 0
		for r in range(nR):
			for c in range(nC):
				cell = grid[r][c]
				if cell == 0:
					vis[r][c] = -1
		for r in range(nR):
			for c in range(nC):
				if vis[r][c] == -1:
					continue
				_max = max(_max, self.dfs(grid, vis, r, c, nR, nC, steps))
		return _max

	def dfs(self, grid, vis, r, c, nR, nC, steps):
		vis[r][c] = -1
		cell = grid[r][c]
		_max = cell
		for step in steps:
			_r = r + step[0]
			_c = c + step[1]
			if 0 <= _r < nR and 0 <= _c < nC and (grid[_r][_c] != 0) and (vis[_r][_c] == 0):
				_max = max(_max, cell + self.dfs(grid, vis, _r, _c, nR, nC, steps))
		vis[r][c] = 0
		return _max


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(r, c):
			res = grid[r][c]
			nxt = 0
			for (ro, co) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				(nr, nc) = (r + ro, c + co)
				if 0 <= nr < M and 0 <= nc < N and grid[nr][nc] and ((nr, nc) not in seen):
					seen.add((nr, nc))
					nxt = max(nxt, dfs(nr, nc))
					seen.remove((nr, nc))
			return res + nxt
		(M, N) = (len(grid), len(grid[0]))
		res = 0
		for i in range(M):
			for j in range(N):
				if grid[i][j]:
					seen = {(i, j)}
					res = max(res, dfs(i, j))
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		res = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				res = max(res, self.find(grid, i, j))
		return res

	def find(self, grid, i, j):
		if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (not grid[i][j]):
			return 0
		current = grid[i][j]
		grid[i][j] = 0
		up = self.find(grid, i - 1, j)
		down = self.find(grid, i + 1, j)
		left = self.find(grid, i, j - 1)
		right = self.find(grid, i, j + 1)
		maxx = max(up, down, left, right)
		grid[i][j] = current
		return maxx + current


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def dfs(i, j, g, c):
			if 0 <= i < m and 0 <= j < n and (grid[i][j] != 0):
				c += grid[i][j]
				tmp = grid[i][j]
				grid[i][j] = 0
				res = max(dfs(i + 1, j, g, c), dfs(i - 1, j, g, c), dfs(i, j + 1, g, c), dfs(i, j - 1, g, c))
				grid[i][j] = tmp
				return res
			return c
		x = [dfs(i, j, grid, 0) for i in range(m) for j in range(n) if grid[i][j] != 0]
		return max(x) if x else 0


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def findSum(row, col, total):
			if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[0])):
				return
			if not grid[row][col]:
				return
			tmp = grid[row][col]
			total += tmp
			grid[row][col] = 0
			if row < len(grid):
				findSum(row + 1, col, total)
			if row >= 0:
				findSum(row - 1, col, total)
			if col < len(grid[0]):
				findSum(row, col + 1, total)
			if col >= 0:
				findSum(row, col - 1, total)
			self.sm = max(self.sm, total)
			grid[row][col] = tmp
		self.sm = 0
		total = 0
		for row in range(len(grid)):
			for col in range(len(grid[row])):
				if grid[row][col]:
					findSum(row, col, total)
					total = 0
		return self.sm


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid or not grid[0]:
			return 0
		self.ans = 0
		(R, C) = (len(grid), len(grid[0]))
		for r in range(R):
			for c in range(C):
				if grid[r][c] == 0:
					continue
				self.dfs(grid, r, c, grid[r][c], set([(r, c)]))
		return self.ans

	def dfs(self, g, r, c, tot, used):
		if tot > self.ans:
			self.ans = tot
		dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
		(R, C) = (len(g), len(g[0]))
		for (dr, dc) in dirs:
			(r2, c2) = (r + dr, c + dc)
			if not (0 <= r2 < R and 0 <= c2 < C):
				continue
			if (r2, c2) in used or g[r2][c2] == 0:
				continue
			used.add((r2, c2))
			self.dfs(g, r2, c2, tot + g[r2][c2], used)
			used.remove((r2, c2))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def getGold(i, j, s, money):
			nonlocal mx
			for (c1, c2) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if (c1, c2) not in s and 0 <= c1 < len(grid) and (0 <= c2 < len(grid[0])) and (grid[c1][c2] != 0):
					s.add((c1, c2))
					getGold(c1, c2, s, money + grid[c1][c2])
					s.remove((c1, c2))
			mx = max(mx, money)
		mx = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				s = set()
				if grid[i][j] != 0:
					s.add((i, j))
					getGold(i, j, s, grid[i][j])
		return mx


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		R = len(grid)
		C = len(grid[0])
		result = 0
		directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

		def dfs(i, j, total=0):
			nonlocal result
			result = max(result, total)
			visited.add((i, j))
			for (dx, dy) in directions:
				(rx, cy) = (i + dx, j + dy)
				if 0 <= rx < R and 0 <= cy < C and ((rx, cy) not in visited) and (grid[rx][cy] != 0):
					dfs(rx, cy, total + grid[rx][cy])
			visited.remove((i, j))
		visited = set()
		for i in range(R):
			for j in range(C):
				if grid[i][j] != 0:
					dfs(i, j, grid[i][j])
		return result


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0

		def dfs(grid, i, j):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (grid[i][j] == 0):
				return 0
			res = grid[i][j]
			grid[i][j] = 0
			cost = res + max(dfs(grid, i + 1, j), dfs(grid, i - 1, j), dfs(grid, i, j + 1), dfs(grid, i, j - 1))
			grid[i][j] = res
			return cost
		max_gold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					max_gold = max(max_gold, dfs(grid, i, j))
		return max_gold


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def BFS(r, c):
			nonlocal best, best_path, R, C, grid
			if grid[r][c] > best:
				best = grid[r][c]
				best_path = set([(r, c)])
			q = [(grid[r][c], r, c, set([(r, c)]))]
			while q:
				next_level = []
				for (t, r, c, p) in q:
					for (i, j) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
						if 0 <= i < R and 0 <= j < C and grid[i][j]:
							if (i, j) not in p:
								next_level.append((t + grid[i][j], i, j, p | set([(i, j)])))
								if t + grid[i][j] > best:
									best = t + grid[i][j]
									best_path = p | set([(i, j)])
				q = next_level
		(R, C) = (len(grid), len(grid[0]))
		best = 0
		best_path = set()
		for r in range(R):
			for c in range(C):
				if grid[r][c]:
					if (r, c) not in best_path:
						BFS(r, c)
		return best


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(grid, i, j):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])):
				return 0
			if grid[i][j] <= 0:
				return 0
			val = grid[i][j]
			grid[i][j] = -1
			ret = val + max(dfs(grid, i - 1, j), dfs(grid, i + 1, j), dfs(grid, i, j - 1), dfs(grid, i, j + 1))
			grid[i][j] = val
			return ret
		result = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				result = max(result, dfs(grid, i, j))
		return result


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.ans = 0

		def dfs(grid, i, j, res):
			res = res + grid[i][j]
			tmp = grid[i][j]
			grid[i][j] = 0
			for (r, c) in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
				if 0 <= r < len(grid) and 0 <= c < len(grid[0]):
					if grid[r][c]:
						dfs(grid, r, c, res)
			grid[i][j] = tmp
			self.ans = max(self.ans, res)
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if grid[i][j]:
					dfs(grid, i, j, 0)
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def helper(i, j):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (grid[i][j] == 0):
				return 0
			val = grid[i][j]
			grid[i][j] = 0
			res = val + max(helper(i + 1, j), helper(i - 1, j), helper(i, j + 1), helper(i, j - 1))
			grid[i][j] = val
			return res
		self.res = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					self.res = max(self.res, helper(i, j))
		return self.res


class Solution:

	def dfs(self, i, j, gold):
		flag = True
		for (ni, nj) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
			if 0 <= ni < self.m and 0 <= nj < self.n and (self.grid[ni][nj] > 0):
				tmp = self.grid[i][j]
				self.grid[i][j] = 0
				self.dfs(ni, nj, gold + self.grid[ni][nj])
				self.grid[i][j] = tmp
				flag = False
		if flag:
			self.ans = max(self.ans, gold)

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(self.m, self.n) = (len(grid), len(grid[0]))
		self.grid = grid
		self.ans = 0
		for i in range(self.m):
			for j in range(self.n):
				if grid[i][j] > 0:
					self.dfs(i, j, grid[i][j])
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(path, curr_sum):
			nonlocal res
			(i, j) = path[-1]
			dirs_lst = [(-1, 0), (1, 0), (0, 1), (0, -1)]
			find = False
			for (di, dj) in dirs_lst:
				ni = i + di
				nj = j + dj
				if 0 <= ni < M and 0 <= nj < N and (grid[ni][nj] > 0):
					find = True
					curr_sum += grid[ni][nj]
					grid[ni][nj] = -grid[ni][nj]
					path.append((ni, nj))
					dfs(path, curr_sum)
					path.pop()
					grid[ni][nj] = -grid[ni][nj]
					curr_sum -= grid[ni][nj]
			if not find:
				res = max(res, curr_sum)
		res = 0
		M = len(grid)
		N = len(grid[0])
		for i in range(M):
			for j in range(N):
				if grid[i][j] > 0:
					grid[i][j] = -grid[i][j]
					dfs([(i, j)], -grid[i][j])
					grid[i][j] = -grid[i][j]
		return res


class Solution:

	def getMaximumGold(self, grid):
		path = []
		total = 0
		self.rLen = len(grid)
		self.cLen = len(grid[0])
		for i in range(self.rLen):
			for j in range(self.cLen):
				if grid[i][j] != 0:
					(retTotal, retPath) = self.dfs(grid, i, j)
					if retTotal > total:
						total = retTotal
						path = retPath
		return total

	def dfs(self, grid, i, j):
		tmp = grid[i][j]
		grid[i][j] = 0
		total = 0
		path = []
		for (newI, newJ) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
			if 0 <= newI < self.rLen and 0 <= newJ < self.cLen and (grid[newI][newJ] != 0):
				(retTotal, retPath) = self.dfs(grid, newI, newJ)
				if retTotal > total:
					total = retTotal
					path = retPath
		grid[i][j] = tmp
		return (total + tmp, path + [[i, j]])


class Solution:

	def getMaximumGold(self, grid: [[int]]) -> int:
		result = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				result = max(self.search(grid, i, j), result)
		return result

	def search(self, grid, x, y):
		if x < 0 or x >= len(grid) or y < 0 or (y >= len(grid[0])):
			return 0
		if grid[x][y] == 0:
			return 0
		result = grid[x][y]
		temp = result
		grid[x][y] = 0
		result += max(self.search(grid, x - 1, y), self.search(grid, x, y - 1), self.search(grid, x + 1, y), self.search(grid, x, y + 1))
		grid[x][y] = temp
		return result


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		seen = set()
		(n, m) = (len(grid), len(grid[0]))
		self.ans = 0

		def dfs(r, c, cur=0):
			seen.add((r, c))
			cur += grid[r][c]
			for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				(x, y) = (r + dx, c + dy)
				if 0 <= x < n and 0 <= y < m and ((x, y) not in seen) and (grid[x][y] != 0):
					dfs(x, y, cur)
			seen.remove((r, c))
			self.ans = max(self.ans, cur)
		for i in range(n):
			for j in range(m):
				if (i, j) not in seen and grid[i][j] != 0:
					dfs(i, j)
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:

		def dfs(x, y, total):
			nonlocal maxTotal, visited
			maxTotal = max(maxTotal, total)
			visited.add((x, y))
			for move in {(1, 0), (0, 1), (-1, 0), (0, -1)}:
				i = x + move[0]
				j = y + move[1]
				if 0 <= i < n and 0 <= j < m and grid[i][j] and ((i, j) not in visited):
					dfs(i, j, total + grid[i][j])
			visited.remove((x, y))
		if not grid or not grid[0]:
			return 0
		n = len(grid)
		m = len(grid[0])
		result = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j]:
					maxTotal = 0
					visited = set()
					dfs(i, j, grid[i][j])
					if maxTotal > result:
						result = maxTotal
		return result


best = 0

def collect(grid, r, c, curr):
	if r >= 0 and c >= 0 and (r < len(grid)) and (c < len(grid[0])) and (grid[r][c] != 0):
		nonlocal best
		val = grid[r][c]
		curr += val
		best = max(best, curr)
		temp = grid[r][c]
		grid[r][c] = 0
		collect(grid, r + 1, c, curr)
		collect(grid, r - 1, c, curr)
		collect(grid, r, c + 1, curr)
		collect(grid, r, c - 1, curr)
		curr -= val
		grid[r][c] = val

class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		nonlocal best
		best = 0
		rows = len(grid)
		cols = len(grid[0])
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] != 0:
					collect(grid, r, c, 0)
		return best


class Solution:

	def dfs(self, grid, i, j, m, n):
		tmp = 0
		if grid[i][j] == 0 or self.visited[i][j] == 1:
			return 0
		self.visited[i][j] = 1
		for (x, y) in self.direction:
			x = i + x
			y = j + y
			if x >= 0 and y >= 0 and (x < m) and (y < n) and (grid[x][y] != 0) and (self.visited[x][y] != 1):
				tmp = max(tmp, self.dfs(grid, x, y, m, n))
		self.visited[i][j] = 0
		return tmp + grid[i][j]

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		m = len(grid)
		n = len(grid[0])
		self.visited = [[0 for _ in range(n)] for _ in range(m)]
		res = 0
		for i in range(m):
			for j in range(n):
				res = max(res, self.dfs(grid, i, j, m, n))
		return res


class Solution:

	def __init__(self):
		self.max_gold = float('-Inf')

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0

		def dfs(current, i, j):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (grid[i][j] == 0):
				return
			current += grid[i][j]
			temp = grid[i][j]
			grid[i][j] = 0
			self.max_gold = max(current, self.max_gold)
			dfs(current, i - 1, j)
			dfs(current, i + 1, j)
			dfs(current, i, j - 1)
			dfs(current, i, j + 1)
			grid[i][j] = temp
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 0:
					dfs(0, i, j)
		return self.max_gold if self.max_gold != float('-Inf') else 0


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.maxGold = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] > 0:
					used = set()
					used.add((i, j))
					self.dfs(i, j, 0, grid, used)
		return self.maxGold

	def dfs(self, i, j, total, grid, used):
		total += grid[i][j]
		if total > self.maxGold:
			self.maxGold = total
		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 ((ni, nj) not in used) and (grid[ni][nj] > 0):
				used.add((ni, nj))
				self.dfs(ni, nj, total, grid, used)
				used.remove((ni, nj))


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		self.res = 0

		def helper(r, c, grid, acc):
			acc += grid[r][c]
			self.res = max(self.res, acc)
			(temp, grid[r][c]) = (grid[r][c], 0)
			for (ir, ic) in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
				if 0 <= r + ir < m and 0 <= c + ic < n and (grid[r + ir][c + ic] > 0):
					helper(r + ir, c + ic, grid, acc)
			grid[r][c] = temp
		for i in range(m):
			for j in range(n):
				if grid[i][j] > 0:
					helper(i, j, grid, 0)
		return self.res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		rows = len(grid)
		cols = len(grid[0])
		moves = [[-1, 0], [0, 1], [1, 0], [0, -1]]
		golds = [(i, j) for i in range(rows) for j in range(cols) if grid[i][j] != 0]
		visited = {}

		def dfs(curr_r, curr_c, curr_gold):
			tmp = []
			for move in moves:
				(new_r, new_c) = (curr_r + move[0], curr_c + move[1])
				if new_r >= 0 and new_r < rows and (new_c >= 0) and (new_c < cols) and (grid[new_r][new_c] != 0) and ((new_r, new_c) not in visited):
					visited[new_r, new_c] = 1
					tmp.append(dfs(new_r, new_c, curr_gold + grid[new_r][new_c]))
					del visited[new_r, new_c]
			if len(tmp) != 0:
				return max(tmp)
			else:
				return curr_gold
		res = float('-inf')
		for g in golds:
			(i, j) = g
			visited[i, j] = 1
			tmp = dfs(i, j, grid[i][j])
			res = max(res, tmp)
			del visited[i, j]
		return res


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		self.ans = 0
		m = len(grid)
		n = len(grid[0])

		def backtrack(i, j, sumup):
			nonlocal n, m
			if i < 0 or i > m - 1 or j < 0 or (j > n - 1) or (grid[i][j] == 0):
				return
			sumup += grid[i][j]
			self.ans = max(self.ans, sumup)
			temp = grid[i][j]
			grid[i][j] = 0
			backtrack(i - 1, j, sumup)
			backtrack(i + 1, j, sumup)
			backtrack(i, j - 1, sumup)
			backtrack(i, j + 1, sumup)
			grid[i][j] = temp
		for i in range(m):
			for j in range(n):
				backtrack(i, j, 0)
		return self.ans


class Solution:

	def getMaximumGold(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		visited = [[False] * n for _ in range(m)]
		self.ans = 0

		def dfs(i, j):
			if i < 0 or i >= m or j < 0 or (j >= n) or visited[i][j] or (grid[i][j] == 0):
				return 0
			visited[i][j] = True
			res = grid[i][j] + max(dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1))
			visited[i][j] = False
			self.ans = max(self.ans, res)
			return res
		for i in range(m):
			for j in range(n):
				if grid[i][j]:
					dfs(i, j)
		return self.ans