求解指定天数内覆盖网格的蚂蚁最小起始位置问题的算法咨询

我面试时碰到这个问题当时完全懵了，现在正试着找解法。一开始我想推演天数从1到4的网格状态，但不知道怎么从第1天过渡到第2天，也不确定这个思路对不对。

问题具体是：蚁群每天可以向8个方向（北、东北、东、东南、南、西南、西、西北）扩张。给定由空区域（空格）和蚂蚁无法穿越的岩石（标记为'R'）组成的网格，以及蚂蚁填满所有空区域所需的天数，求蚂蚁所需的最小起始位置数量。

示例1 #

grid = [[" ", " ", " ", " ", " "],        days = 3
        [" ", " ", " ", " ", " "],
        [" ", " ", " ", " ", " "],
        [" ", " ", " ", " ", " "],
        [" ", " ", " ", " ", " "]]

答案：1

第1天状态：

[[" ", " ", " ", " ", " "],   
 [" ", " ", " ", " ", " "],
 [" ", " ", "A", " ", " "],
 [" ", " ", " ", " ", " "],
 [" ", " ", " ", " ", " "]]

第2天状态：

[[" ", " ", " ", " ", " "],   
 [" ", "A", "A", "A", " "],
 [" ", "A", "A", "A", " "],
 [" ", "A", "A", "A", " "],
 [" ", " ", " ", " ", " "]]

第3天状态：

[["A", "A", "A", "A", "A"],   
 ["A", "A", "A", "A", "A"],
 ["A", "A", "A", "A", "A"],
 ["A", "A", "A", "A", "A"],
 ["A", "A", "A", "A", "A"]]

示例2 #

grid = [[" ", " ", " ", " ", "R", " "],        days = 4
        [" ", " ", " ", " ", "R", " "],
        [" ", " ", " ", " ", "R", "R"],
        [" ", " ", " ", " ", " ", " "],
        [" ", " ", " ", " ", " ", " "],
        [" ", "R", " ", "R", "R", "R"],
        [" ", "R", "R", "R", " ", " "],
        [" ", " ", " ", " ", " ", " "]]

答案：3

第1天状态：

[[" ", " ", " ", " ", "R", "A"], 
 [" ", " ", " ", " ", "R", " "],
 [" ", " ", "A", " ", "R", "R"],
 [" ", " ", " ", " ", " ", " "],
 [" ", " ", " ", " ", " ", " "],
 [" ", "R", " ", "R", "R", "R"],
 [" ", "R", "R", "R", " ", " "],
 [" ", " ", "A", " ", " ", " "]]

第2天状态：

[[" ", " ", " ", " ", "R", "A"], 
 [" ", "A", "A", "A", "R", "A"],
 [" ", "A", "A", "A", "R", "R"],
 [" ", "A", "A", "A", " ", " "],
 [" ", " ", " ", " ", " ", " "],
 [" ", "R", " ", "R", "R", "R"],
 [" ", "R", "R", "R", " ", " "],
 [" ", "A", "A", "A", " ", " "]]

第3天状态：

[["A", "A", "A", "A", "R", "A"], 
 ["A", "A", "A", "A", "R", "A"],
 ["A", "A", "A", "A", "R", "R"],
 ["A", "A", "A", "A", "A", " "],
 ["A", "A", "A", "A", "A", " "],
 [" ", "R", " ", "R", "R", "R"],
 ["A", "R", "R", "R", "A", " "],
 ["A", "A", "A", "A", "A", " "]]

第4天状态：

[["A", "A", "A", "A", "R", "A"], 
 ["A", "A", "A", "A", "R", "A"],
 ["A", "A", "A", "A", "R", "R"],
 ["A", "A", "A", "A", "A", "A"],
 ["A", "A", "A", "A", "A", "A"],
 ["A", "R", "A", "R", "R", "R"],
 ["A", "R", "R", "R", "A", "A"],
 ["A", "A", "A", "A", "A", "A"]]

内容的提问来源于stack exchange，提问作者TreeWater