c - 给定一个矩阵和一些规则，设置二进制矩阵的所有位所需的最少天数是多少

Question

给定一个矩阵和一些规则，设置二进制矩阵的所有位所需的最少天数是多少规则:

1. 只有值为“1”的单元格才能在 1 天内设置距离为 1 个单位的周围相邻单元格。
2. 单元格可以水平或垂直设置。对角线不被视为邻居。

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。

最快的算法是什么？

Answer 1

最快的算法的复杂度等于 O(M)，其中 M -- 像素数，如果您有矩阵 NxN，那么您的复杂度为 O(N*N)。

最简单的算法是将每个值为 1 的像素放在一个列表中，然后遍历该列表，将邻居涂黑并将它们放入列表中，然后使用该列表找到新的邻居绘画并添加到列表中。显然没有像素会被绘制两次，因此该算法与像素数成线性关系。

关于天数，最坏的情况是2*N，此时只有一个角像素设置为1。