给定一个矩阵和一些规则,设置二进制矩阵的所有位所需的最少天数是多少 规则:
- 只有值为“1”的单元格才能在 1 天内设置距离为 1 个单位的周围相邻单元格。
- 单元格可以水平或垂直设置。对角线不被视为邻居。
given a matrix(A) of rows(N), and columns(M)
A=[
0 1 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
]
after 1 day
A=[
1 1 1 0 1
0 1 0 1 1
0 0 1 1 1
0 1 1 1 0
]
after 2 day
A=[
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
1 1 1 1 1
]
after 3 day
A=[
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
]
设置所有单元格所需的最少天数为 3。
最快的算法是什么?
最佳答案
最快的算法的复杂度等于 O(M),其中 M -- 像素数,如果您有矩阵 NxN
,那么您的复杂度为 O(N*N)。
最简单的算法是将每个值为 1
的像素放在一个列表中,然后遍历该列表,将邻居涂黑并将它们放入列表中,然后使用该列表找到新的邻居绘画并添加到列表中。显然没有像素会被绘制两次,因此该算法与像素数成线性关系。
关于天数,最坏的情况是2*N
,此时只有一个角像素设置为1
。
关于c - 给定一个矩阵和一些规则,设置二进制矩阵的所有位所需的最少天数是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58603415/