使用这些规则在最短时间内访问网格中的每个单元格？
Visiting every cell in grid in the minimum time with these rules?
样本被放置在 n X m 大小的网格中，网格被分成 1 X 1 个单元格。
按照以下规则展开。
如果在时间t，样本占据(x ,y)，那么在时间t+1它最多可以扩展到[=25=中的任意两个单元格](x+1,y), (x-1,y), (x,y+1), (x,y-1).
例如如果在t = 0秒时，如果样本占据(4, 5)，那么在时间t = 1秒时，网格的状态可以是以下任何一种
1. specimen at (4,5), (5,5) and (3,5).
2. specimen at (4,5), (5,5) and (4,6).
3. specimen at (4,5), (5,5) and (4,4).
4. specimen at (4,5), (3,5) and (4,6).
5. specimen at (4,5), (3,5) and (4,4).
6. specimen at (4,5), (4,6) and (4,4).
注-在t=2秒时，可以从t=1时样本占据的所有点展开
我打算采用贪心策略，广度优先搜索，尝试每一步至少标记两个节点，在一步不能标记两个节点后，我把剩下的加起来。这种方法会给出最佳结果吗？
如果不是怎么解决？
考虑距离样本最远的场地角。例如，如果样本位于角落 (1,1)，则最远的角落将为 (n,m)。
假设到这个角的距离沿 x 轴 dX 和沿 y 轴 dY。最重要的见解是，无论您选择哪种策略，您至少需要 dX+dY 步才能殖民这个最远的角落。这很容易确定，如果有人看到，在 t 步之后，没有细胞可以被比曼哈顿距离 t 更远的样本定殖。
现在，如果我给你一个在 dX+dY 步内殖民整个领域的策略，那么这是一个最优策略，因为任何策略都不会在 dX+dY-1 步之后殖民到最远的角落.
我的策略如下：
阶段：对于 dX 步长在两个 x 方向上增长（只要两个方向都可能，否则仅在最远角的方向上）。在这个阶段之后，一整行的字段被殖民（因为我们选择的是最远的）。
阶段：dY 步在 y 方向上增长：在这个阶段的第一步之后有 3 个完整的殖民行，在第二步之后 - 5，依此类推直到dY整个场地被殖民，因为（同上）选择的角落是最远的。
所以最少需要的时间是dX+dY。
样本被放置在 n X m 大小的网格中，网格被分成 1 X 1 个单元格。
按照以下规则展开。
如果在时间t，样本占据(x ,y)，那么在时间t+1它最多可以扩展到[=25=中的任意两个单元格](x+1,y), (x-1,y), (x,y+1), (x,y-1).
例如如果在t = 0秒时，如果样本占据(4, 5)，那么在时间t = 1秒时，网格的状态可以是以下任何一种
1. specimen at (4,5), (5,5) and (3,5).
2. specimen at (4,5), (5,5) and (4,6).
3. specimen at (4,5), (5,5) and (4,4).
4. specimen at (4,5), (3,5) and (4,6).
5. specimen at (4,5), (3,5) and (4,4).
6. specimen at (4,5), (4,6) and (4,4).
注-在t=2秒时，可以从t=1时样本占据的所有点展开
我打算采用贪心策略，广度优先搜索，尝试每一步至少标记两个节点，在一步不能标记两个节点后，我把剩下的加起来。这种方法会给出最佳结果吗？
如果不是怎么解决？
考虑距离样本最远的场地角。例如，如果样本位于角落 (1,1)，则最远的角落将为 (n,m)。
假设到这个角的距离沿 x 轴 dX 和沿 y 轴 dY。最重要的见解是，无论您选择哪种策略，您至少需要 dX+dY 步才能殖民这个最远的角落。这很容易确定，如果有人看到，在 t 步之后，没有细胞可以被比曼哈顿距离 t 更远的样本定殖。
现在，如果我给你一个在 dX+dY 步内殖民整个领域的策略，那么这是一个最优策略，因为任何策略都不会在 dX+dY-1 步之后殖民到最远的角落.
我的策略如下：
阶段：对于
dX步长在两个 x 方向上增长（只要两个方向都可能，否则仅在最远角的方向上）。在这个阶段之后，一整行的字段被殖民（因为我们选择的是最远的）。阶段：
dY步在 y 方向上增长：在这个阶段的第一步之后有 3 个完整的殖民行，在第二步之后 - 5，依此类推直到dY整个场地被殖民，因为（同上）选择的角落是最远的。
所以最少需要的时间是dX+dY。