algorithm - 找到矩阵中最后一个像螺旋一样行走的正方形

Question

给定矩阵 A x A 和多个运动 N。

像螺旋一样行走:

1. 如果可能的话，那么
2. 尽可能降低，然后
3. 尽可能离开，然后
4. 尽可能向上，重复直到获得N。

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

在此示例中，最终的正方形为 (4; 7)。

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

Answer 1

是的，可以计算出答案。

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

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

(另一个注意点:这个答案与 Nyavro's answer 非常相似，只是我避免了这里的递归。)

---

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

• (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

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

---

现在我们知道对角线上有哪些标签，我们可以计算出必须从 K 中删除多少层(例如 A x A )矩阵，使最终的正方形位于边缘。如果我们这样做，那么就回答了我们的问题

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) ;和
• 如果 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