【leetcode】1219. Path with Maximum Gold
2024-10-20 20:46:57
题目如下:
In a gold mine
grid
of sizem * 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.
解题思路:DFS或者BFS都可以。本题主要是需要记录遍历过的节点,防止重复遍历陷入死循环。我的记录方法是利用整数的位操作,给grid中每个节点都分配一个序号,按从左往右从上往下的顺序,(0,0)是2^0,(0,1)是2^1次方,依次类推。
代码如下:
class Solution(object):
def getMaximumGold(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def getNumber(x,y):
v = x*len(grid[0]) + y
return 2**v
res = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 0:continue
count = grid[i][j]
flag = 0
queue = [(i,j,count,flag | getNumber(i,j))]
direction = [(0,1),(0,-1),(1,0),(-1,0)]
while len(queue) > 0:
x,y,count,flag = queue.pop(0)
res = max(res,count)
for (x1,y1) in direction:
if x1 + x >= 0 and x1+x < len(grid) and y+y1 >=0 and y+y1 < len(grid[0]) and grid[x+x1][y+y1] != 0 \
and flag & getNumber(x1+x,y1+y) == 0:
new_count = count + grid[x1+x][y1+y]
queue.append((x+x1,y+y1,new_count,flag | getNumber(x1+x,y1+y)))
return res
最新文章
- InstallShield Limited Edition制作安装文件
- jQuery—DOM操作
- MiniDao-PE精简版
- 矩阵乘法快速幂 codevs 1250 Fibonacci数列
- zoj1107 FatMouse and Cheese
- tomcat编译通过问题
- Prometheus : 入门
- Elixir的Phoenix框架:请求处理之道
- linux系统磁盘空间满了怎么办看完这篇文章之后就知道怎么解决了
- tornado web高级开发项目
- 第二十节,使用RNN网络拟合回声信号序列
- 【OpenCV】SIFT原理与源码分析:DoG尺度空间构造
- 【css】适配iphoneX
- 理解linux下的load
- Spyder设置代码自动补全
- php ajax登录注册
- Extjs gridpanel 合并单元格
- PAT 1001 A+B Fotmat
- D3.js 入门教程
- vue2.0实现页面刷新时某个input获得focus