algorithm - 用平面向量表示的网格扫描(遍历)

Question

我有一个用平面向量表示的网格，即:

-------------
| 6 | 7 | 8 |
-------------
| 3 | 4 | 5 |
-------------
| 0 | 1 | 2 |
-------------

我访问索引从 0 到 grid.size()-1 的元素。我想实现快速扫描方法。该方法的主要目的是它执行 sweeps，即在特定方向上遍历网格。对于 2D 情况:

扫描 1:右上

for [row = 0 : nrows-1]
    for [col = 0 : ncols-1] --> Result: 0 1 2 3 4 5 6 7 8

扫描 2:左上

for [row = 0 : nrows-1]
    for [col = ncols-1 : 0] --> Result: 2 1 0 5 4 3 8 7 6

扫描 3:右下

for [row = nrows-1 : 0]
    for [col = 0 : ncols-1] --> Result: 6 7 8 3 4 5 0 1 2

扫描 4:左下

for [row = nrows-1 : 0]
    for [col = ncols-1 : 0] --> Result: 8 7 6 5 4 3 2 1 0 

然后计算idx = row*ncols + col。

这个实现很简单，它也可以推广到 n 维度，当只是嵌套 for 循环时。然而，我正在研究一个 n 维的实现，我试图在两个循环中概括它:

while (keepSweeping)
    ++sweep;
    for (idx = init, idx == end, idx += inc)
         // Traverse the grid

计算 init、end 和 inc 真的很有挑战性。此外，inc 还依赖于 ncols 并会动态变化。例如，对于 sweep 2 inc = -1，但是每 ncols 次 inc = -1 + 2*ncols，所以我实现了从 0 到 5。

关于如何做的任何帮助？我首先关注 2D 案例。

编辑: 我看到了这些线程 http://www.cplusplus.com/forum/beginner/68434/ variable nested for loops建议递归地实现循环。由于我正在寻找最佳性能，您认为这是个好主意吗？

谢谢!

Answer 1

好的，这是我尝试在 2D 情况下仅使用一个循环来回答您的问题。希望这与您正在寻找的东西相距不远:

// ****** INITIALIZATION ******
int ncols = 4; // number of columns
int nrows = 3; // number of rows
boolean right = true; // direction of sweep on horizontal axis
boolean top = true; // direction of sweep on vertical axis
int counter = 0; // number of positions explored
if (right) {
    colIterator = 0;
}
else {
    colIterator = ncols - 1;
}
if (top) {
    rowIterator = 0;
}
else {
    rowIterator = nrows - 1;
}

// ****** CONTINUATION CONDITION ******
while (counter != nrows*ncols) {

    // ****** DO SOMETHING ******
    System.out.println(rowIterator*ncols + colIterator);

    // ****** PROGRESSION PHASE ******
    counter++;
    // Have we completed a row?
    if ((counter % ncols) == 0) {
        if (top) {
            // We have to move up
            rowIterator++;
        }
        else {
            // we have to move down
            rowIterator--;
        }
        if (right) {
            colIterator = 0;
        }
        else {
            colIterator = ncols - 1;
        }
    }
    else {
        // We have not yet completed a row
        if (right) {
            // We have to move right
            colIterator++;
        }
        else {
            // or left
            colIterator--;
        }
    }
}

注意:此代码已通过 Groovy 测试。

一些高层解释:它适用于一个循环，因为在二维中，我们可以找到我们想要做的工作的全局进度指标 (这里这个指标是 counter 变量)并且可以使用指标来确定，在循环的每次迭代中，我们是否通过使用模数操作完成了一行。

我认为仅用一个循环就可以将此算法推广到更高维度(即高于 2)在数学上是不可能的，因为没有数学运算符会告诉我们是否已经完成了一个上的部分工作给定维度，应该开始处理外部维度(这里，模数告诉我们必须修改 rowIterator 因为我们已经到达网格的边界，但在维度 3 或高于 3 的情况下，要使用的数学运算符是什么？)。

祝你好运，请发布你的发现，这是一个有趣的挑战。