Outside-In 2D 数组算法

Question

我收到了一系列非负整数。

43 18 5 67 1 72 16 17 15 93 38 6 83 10 49 98 7 47 61 52 71 79 82 52 8

我需要把它从外向内存储在m * n数组中。如下所示：

m = 5
n = 5

然后，我需要计算二维数组的某一部分的总和。（我已经完成了这部分）。

我理想的存储数字的方法：

 1. Initialize starti,startj = 0.
 2. Initialize endi = m , endj = n.
 3. Store the remaining numbers in array[starti][j], where j starts from startj and ends at endj.
 4. Store the remaining numbers in array[i][endj], where i starts from starti and ends at endi.
 5. Store the remaining numbers in array[endi][j], where j starts from endj and ends at startj.
 6. Store the remaining numbers in array[i][endj], where i starts from endi and ends at starti.
 7. Decrement endi and endj by 1. 
 8. Increment starti and start j by 1.
 9. Repeat the steps 3 - 8 until the last number is stored.

问题: 有没有更好的方法来解决这个问题?

附加信息: 我一直在试图想出一个公式来找到在执行所有这些操作之前最后一个元素存储的位置，但是我失败了。

- Thanakron Tandavas

---

你已经实现了你的方法吗？这个方法产生了正确的输出，但你正在寻找更好的方法吗？还是这个方法没有产生正确的输出？ - taskinoor

我还没有实现这些方法，但我相信它们会产生正确的输出。 - Thanakron Tandavas

你应该实现一个爬虫来找出数字#N在一个W*H维度的数组中应该放置的位置，而不是使用公式。 - Vesper

Answer 1

这里有一种方法。

首先，您可以从递归思考开始。

有一个方法，其签名类似于 `fill(m,n,starting_position, direction)`。

递归版本将看起来像：

fill(m,n, starting_position, direction) {

// If m=0 or n=0 you have a base case.
// Start at starting position, and fill in the direction.
// Decrement m or n, depending on the direction
// Compute new starting position and direction
// Recursively call fill with the updated m,n, starting_pos, direction
}

请注意，此方法是尾递归的，因此您可以摆脱递归并将其替换为while循环，而while循环的条件则从基本情况派生。

- Knoothe

---

这不是我的作业。这是我国本地ACM-ICPC练习题的实践问题。 - Thanakron Tandavas