j*****d
发帖数: 1625 | 1 给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
方向的人，耗时1天。
问用多少天可以把所有可以被感染的1都感染成2.
我写的BFS，很简单的。请问这一题如何DP来做呢？ |
j******o
发帖数: 4219 | |
j*****d
发帖数: 1625 | 3 如何dp，我真是没想出来。
【在 j******o 的大作中提到】
: LC 994, 用DP反而麻烦吧
|
j*****d
发帖数: 1625 | |
j*****d
发帖数: 1625 | 5 你用dp写出来了么？
【在 j******o 的大作中提到】
: LC 994, 用DP反而麻烦吧
|
l******r
发帖数: 1 | 6 试一下这个
DP[i][j][t]是t次迭代之后position i，j被感染需要的天数
最后return max(DP[i][j][m*n] where M[i][j] = 1, m = len(M), n = len(M[0])
那
DP[i][j][t] = 1 + min_{x,y where M[x][y] != 0 and x,y is neighbor of i, j}
DP[x][y][t - 1]
初始条件DP[i][j][t] = 0 if M[i][j] = 2 else DP[i][j][t] = infinity
【在 j*****d 的大作中提到】
: 你用dp写出来了么？
|
l******r
发帖数: 1 | 7 这是code
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
DP = [[[float('inf') for k in range(m*n)] for j in range(n)] for i
in range(m)]
for i in range(m):
for j in range(n):
for t in range(m*n):
if grid[i][j] == 2:
DP[i][j][t] = 0
else:
DP[i][j][t] = float('inf')
for t in range(1, m*n):
for i in range(m):
for j in range(n):
if i + 1 < m and grid[i + 1][j] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i + 1][j][t -
1])
if i - 1 >= 0 and grid[i - 1][j] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i - 1][j][t -
1])
if j + 1 < n and grid[i][j + 1] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i][j + 1][t -
1])
if j - 1 >= 0 and grid[i][j - 1] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i][j - 1][t -
1])
res = -float('inf')
noOnesFlag = True
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and DP[i][j][m*n - 1] > res:
res = DP[i][j][m*n - 1]
noOnesFlag = False
if noOnesFlag == True:
return 0
return res if res < float('inf') else -1
【在 j*****d 的大作中提到】
: 你用dp写出来了么？
|
g****y
发帖数: 2810 | 8 把所有的感染者放入一个队列，每天就是把新感染的人放入一个新队列，等到新队列里
面没人了就是最后一天。
这样就可以O（n) n是所有的非0格子。
：给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
：方向的人，耗时1天。 |
C*****y
发帖数: 42 | |
d******w
发帖数: 2213 | 10 你这是BFS，他要DP。
4个
【在 g****y 的大作中提到】
: 把所有的感染者放入一个队列，每天就是把新感染的人放入一个新队列，等到新队列里
: 面没人了就是最后一天。
: 这样就可以O（n) n是所有的非0格子。
:
: ：给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
: ：方向的人，耗时1天。
|
|
|
p**r
发帖数: 5853 | 11 好评！我想了一会儿就放弃了，
并且心中有一万只草泥马跑过，这不吃饱了撑了。
【在 l******r 的大作中提到】
: 这是code
: class Solution:
: def orangesRotting(self, grid: List[List[int]]) -> int:
: m = len(grid)
: n = len(grid[0])
: DP = [[[float('inf') for k in range(m*n)] for j in range(n)] for i
: in range(m)]
: for i in range(m):
: for j in range(n):
: for t in range(m*n):
|
j*****d
发帖数: 1625 | 12 我给你看看他给我的feedback，你就知道什么叫天竺威武了。
【在 p**r 的大作中提到】
: 好评！我想了一会儿就放弃了，
: 并且心中有一万只草泥马跑过，这不吃饱了撑了。
|
l******r
发帖数: 1 | 13 50 伪币呢？
【在 j*****d 的大作中提到】
: 我给你看看他给我的feedback，你就知道什么叫天竺威武了。
|
p**r
发帖数: 5853 | 14 他给你了吗？
我作为路人赞助30，因为talking is cheap，show me your code
【在 l******r 的大作中提到】
: 50 伪币呢？
|
l******r
发帖数: 1 | 15 他没给啊。所以跟他开个玩笑。我又不需要伪币。
就想看看他是不是守信用。
【在 p**r 的大作中提到】
: 他给你了吗？
: 我作为路人赞助30，因为talking is cheap，show me your code
|
j*****d
发帖数: 1625 | 16 不好意思，以为这个帖子没有人追了。现在给你。
【在 l******r 的大作中提到】
: 50 伪币呢？
|
j*****d
发帖数: 1625 | 17 写个java更好了，已经转了。
【在 l******r 的大作中提到】
: 他没给啊。所以跟他开个玩笑。我又不需要伪币。
: 就想看看他是不是守信用。
|
j*****d
发帖数: 1625 | 18 我给了。
【在 p**r 的大作中提到】
: 他给你了吗？
: 我作为路人赞助30，因为talking is cheap，show me your code
|
j*****d
发帖数: 1625 | 19 请确认收到，信用事大。
【在 l******r 的大作中提到】
: 他没给啊。所以跟他开个玩笑。我又不需要伪币。
: 就想看看他是不是守信用。
|
l******r
发帖数: 1 | 20 给了。多谢收到。返还给pker他的30了。
找工作好烦啊。面试都拿不到。
【在 j*****d 的大作中提到】
: 请确认收到，信用事大。
|
j*****d
发帖数: 1625 | 21 我是面试onsite拿到手软，可是，到处碰到这类3+黑，没有办法。请观看另外一帖，迷
思。
【在 l******r 的大作中提到】
: 给了。多谢收到。返还给pker他的30了。
: 找工作好烦啊。面试都拿不到。
|
