algorithm - 之字形填充算法？

Question

如何制作一种算法，以锯齿形填充任意大小的网格，如下图所示？

这是我的算法，它不起作用。 (改为从左下角到右上角):

x1 = 0;
y1 = grid_h-1;
var a = 0;
put(x1,y1);

while(!((x1 = grid_w-1) and (y1 = 0))) { //If it isn't at the top right corner
    if a = 2 {
        x1 += 1;
        put(x1,y1);
        while(x1 != grid_w-1) { //While x1 isn't at the right
            //Go diagonally down
            x1 += 1;
            y1 += 1;
            put(x1,y1);
        }
        y1 -= 1;
        put(x1,y1);
        while(y1 != 0) { //While y1 isn't at the top
            //Go diagonally up
            x1 -= 1;
            y1 -= 1;
            put(x1,y1);
        }
    } else if a = 1 {
        while(x1 != grid_w-1) { //While x1 isn't at the right
            //Go diagonally down
            x1 += 1;
            y1 += 1;
            put(x1,y1);
        }
        y1 -= 1;
        put(x1,y1);
        while(y1 != 0) { //While y1 isn't at the top
            //Go diagonally up
            x1 -= 1;
            y1 -= 1;
            put(x1,y1);
        }
        x1 += 1;
        put(x1,y1);
    } else {
        y1 -= 1;
        if (y1 = 0) { a = 1; } //At top?
        put(x1,y1);
        while(y1 != grid_h-1) { //While y1 isn't at the bottom
            //Go diagonally down
            x1 += 1;
            y1 += 1;
            put(x1,y1);
        }

        x1 += 1;
        put(x1,y1);
        while(x1 != 0) { //While x1 isn't at the left
            //Go diagonally up
            x1 -= 1;
            y1 -= 1;
            put(x1,y1);
            if (y1 = 0) { a = 2; } //At top?
        }
    }
}

有什么更简单的方法吗？

Answer 1

这里的关键观察是当Manhattan distance左上角的方 block 是奇数，否则是西南方 block 。

当然，您必须考虑击中其中一个边缘。例如，当您向西南走并碰到底部或南边时，您会向东移动；当您击中左边缘或西边缘时，您将向南移动。您可以捕获三种情况(南边、西边、无拘无束的运动)，也可以在走出边界时移动并纠正您的位置。

点击广告后，您的新位置应该会让您转向另一条路。也就是说，每次校正涉及奇数个步骤。 (这里的步数是您正常到达的地点和最终到达的地点之间的曼哈顿距离。)

如果您的之字形算法工作正常，您将最终访问每个单元格一次。也就是说，您进行 h × w 移动，其中 h 和 w 是高度和宽度。您可以将其用作终止标准，而不是检查您是否在最后一个方格中。

这是此解决方案的示例代码。附加的 bool 参数 down 指定第一步是向下还是向左。

function zigzag(width, height, down) {
    var x = 0;
    var y = 0;
    var n = width * height;

    if (down === undefined) down = false;

    while (n--) {
        var even = ((x + y) % 2 == 0);

        put(x, y);

        if (even == down) {             // walk southwest
            x--;
            y++;

            if (y == height) {
                y--; x += 2;
            }
            if (x < 0) x = 0;
        } else {                        // walk northeast
            x++;
            y--;

            if (x == width) {
                x--; y += 2;
            }
            if (y < 0) y = 0;
        }
    }

    return res;
}