在像螺旋一样行走的矩阵中找到最后一个方块

Question

给定矩阵 A x A 和一些移动 N。

像螺旋一样行走：

尽可能正确，然后
尽可能向下，然后
尽可能离开，然后
尽可能向上，重复直到得到 N。

带示例的图片 (A = 8; N = 36)

在这个例子中，最后的正方形是 (4; 7)。

我的问题是：是否可以使用通用公式来解决这个问题？

Answer 1

我将在这里提出一个相对简单的解决方法，它在 O(A^2) 时间内生成所有索引，以便以后可以在 O(1) 中访问任何 N。但是，如果 A 发生变化，我们将不得不再次执行该算法，这将再次消耗 O(A^2) 时间。

我建议您使用这样的结构来存储索引以访问您的矩阵：

Coordinate[] indices = new Coordinate[A*A]

其中 Coordinate 只是一对 int.

然后您可以使用一些循环来填充 indices 数组：（此实现使用基于 1 的数组访问。如果这是一个问题，请相应地更正包含 i、sentinel 和 currentDirection 的表达式。）

    Coordinate[] directions = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    Coordinate c = new Coordinate(1, 1);
    int currentDirection = 1;
    int i = 1;
    int sentinel = A;
    int sentinelIncrement = A - 1;
    boolean sentinelToggle = false;

    while(i <= A * A) {
        indices[i] = c;
        if (i >= sentinel) {
            if (sentinelToggle) {
                sentinelIncrement -= 1;
            }
            sentinel += sentinelIncrement;
            sentinelToggle = !sentinelToggle;
            currentDirection = currentDirection mod 4 + 1;
        }
        c += directions[currentDirection];
        i++;
    }

好吧，开始解释：我正在使用一个名为 sentinel 的变量来跟踪我需要切换方向的位置（只需循环遍历数组 directions 即可切换方向） . sentinel 的值以这样一种方式递增，即它始终具有我们螺旋中角的索引。在您的示例中，哨兵将采用值 8、15、22、28、34、39 等。注意"sentinel"的索引两次增加7（8, 15 = 8 + 7, 22 = 15 + 7），然后增加6（28 = 22 + 6, 34 = 28 + 6），然后增加5等等。在我的 while 循环中，我为此使用了布尔值 sentinelToggle 。每次我们碰到螺旋的一个角（这正是 iff i == sentinel，这是 if 条件出现的地方），我们将哨兵增加 sentinelIncrement 和改变我们前进的方向。如果 sentinel 以相同的值递增两次，则 if 条件 if (sentinelToggle) 将为真，因此 sentinelIncrement 减一。我们必须减少 sentinelIncrement 因为我们的螺旋会随着我们的前进而变小。

只要 i <= A*A，即只要我们的数组 indices 仍然有零条目，就会继续。

请注意，这不会为您提供关于 N（即 O(1) ）的螺旋坐标的封闭公式；相反，它生成占用 O(A^2) 时间的所有 N 的索引，然后通过简单地调用 indices[N].[=36 来保证 O(1) 的访问=]

O(n^2) 希望不会受到太大伤害，因为我假设您还需要在某个点填充矩阵，这也需要 O(n^2)。

如果效率是个问题，请考虑摆脱 sentinelToggle 这样它就不会搞乱分支预测。相反，每次满足 while 条件时递减 sentinelIncrement。要为您的 sentinel 值获得相同的效果，只需在 (A - 1) * 2 开始 sentinelIncrement 并且每次满足 if 条件时，执行：

sentinel += sentinelIncrement / 2

整数除法与每秒钟只减少sentinelIncrement具有相同的效果。我没有在我的版本中做这整件事，因为我认为仅使用布尔值可能更容易理解。

希望对您有所帮助！

Answer 2

以下是可能的解决方案：

f a n | n < (a-1)*1 = (0, n)
      | n < (a-1)*2 = (n-(a-1), a-1)
      | n < (a-1)*3 = (a-1, 3*(a-1)-n)
      | n < (a-1)*4 = (4*(a-1)-n, 0)
      | otherwise = add (1,1) (f (a-2) (n - 4*(a-1))) where
          add (x1, y1) (x2, y2) = (x1+x2, y1+y2)

这是一个基本的解决方案，它可能会被进一步泛化——我只是不知道你需要多少泛化。这样你就明白了。

编辑

备注：

解决方案是基于 0 的索引
需要检查是否存在 (n >= a*a)

Answer 3

是，可以算出答案

这样做有助于将问题分成三个部分。

（注意：为了简化数学运算，我从零开始计数。这意味着您必须在答案的某些部分添加 1。例如，我对A = 8, N = 36 将是最后一个正方形 (3; 6)，其标签为 35。）

（另一个注意：这个答案与非常相似，只是我在这里避免了递归。）

在第一部分中，您计算对角线上的标签：

(0; 0) 有标签 0。
(1; 1) 有标签 4*(A-1)。周期可以平均分为四个部分（用你的标签：1..7、8..14、15..21、22..27）。
(2; 2) 有标签 4*(A-1) + 4*(A-3)。围绕 A x A 矩阵进行一个循环后，您的下一个循环将围绕 (A - 2) x (A - 2) 矩阵进行。

等等。现在有很多方法可以找出 (K; K)（当 0 < K < A/2 时）的一般规则。我只会选择最容易显示的那个：

4*(A-1) + 4*(A-3) + 4*(A-5) + ... + 4*(A-(2*K-1)) =
4*A*K - 4*(1 + 3 + 5 + ... + (2*K-1)) =
4*A*K - 4*(K + (0 + 2 + 4 + ... + (2*K-2))) =
4*A*K - 4*(K + 2*(0 + 1 + 2 + ... + (K-1))) =
4*A*K - 4*(K + 2*(K*(K-1)/2)) =
4*A*K - 4*(K + K*(K-1)) =
4*A*K - 4*(K + K*K - K) =
4*A*K - 4*K*K =
4*(A-K)*K

（注意：在 A = 8 和 K = 1 时检查 4*(A-K)*K = 28。将此与示例中 (2; 2) 处的标签进行比较。）

既然我们知道对角线上的标签是什么，我们就可以计算出我们必须从 A x A 矩阵中删除多少层（比如 K），以便最终的正方形在边缘。如果我们这样做，那么回答我们的问题

What are the coordinates (X; Y) when I take N steps in a A x A matrix?

可以通过计算这个K和代替解决问题

What are the coordinates (X - K; Y - K) when I take N - 4*(A-K)*K steps in a (A - 2*K) x (A - 2*K) matrix?

为此，我们应该找到最大的整数 K 使得 K < A/2 和 4*(A-K)*K <= N.

解决方法是K = floor(A/2 - sqrt(A*A-N)/2)。

剩下的就是找出 N 沿某个 A x A 矩阵边缘的正方形的坐标：

如果0*E <= N < 1*E，坐标为(0; N)；
如果1*E <= N < 2*E，坐标为(N - E; E)；
如果2*E <= N < 3*E，坐标为(E; 3*E - N)；和
if 3*E <= N < 4*E,坐标为(4*E - N; 0).

这里，E = A - 1.

总而言之，这是一个天真的（layerNumber 由于浮动不准确而对 a 的大值给出了错误的答案）Haskell 这个答案的实现：

finalSquare :: Integer -> Integer -> Maybe (Integer, Integer)
finalSquare a n
    | Just (x', y') <- edgeSquare a' n' = Just (x' + k, y' + k)
    | otherwise = Nothing
  where
    k = layerNumber a n
    a' = a - 2*k
    n' = n - 4*(a-k)*k

edgeSquare :: Integer -> Integer -> Maybe (Integer, Integer)
edgeSquare a n
    | n < 1*e = Just (0, n)
    | n < 2*e = Just (n - e, e)
    | n < 3*e = Just (e, 3*e - n)
    | n < 4*e = Just (4*e - n, 0)
    | otherwise = Nothing
  where
    e = a - 1

layerNumber :: Integer -> Integer -> Integer
layerNumber a n = floor $ aa/2 - sqrt(aa*aa-nn)/2
  where
    aa = fromInteger a
    nn = fromInteger n

在像螺旋一样行走的矩阵中找到最后一个方块

Find final square in matrix walking like a spiral

language-agnostic

algorithm

math

dynamic-programming