algorithm - 以更小的螺旋线穿过方阵

Question

我想要做的是一种算法，它通过一个闭合螺旋模式的矩阵，如下所示：

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

解决这个问题的最简单方法是什么？

我的想法：

• 角落或障碍物检测。
• 有一种程序化的方式可以垂直和反向下降。
• 有一种方法可以检测一个元素已经被访问过。

PS：不知道如何处理大小不是正方形或宽度是偶数的情况。

Answer 1

您不需要每个单元格的已访问概念，只需一个变量来指示您的距离。

下面是一些（未经广泛测试的）Java 代码来执行此操作。

它应该是非常可读的。

  // initialize
  int w = 5, h = 7;
  int[][] arr = new int[w][h];

  // do the work
  int count = 1;
  for (int i = 0; count <= w*h; i++)
  {
     // go right
     for (int x = i; x < w-i && count <= w*h; x++)
        arr[x][i] = count++;

     // go down
     for (int y = i+1; y < h-i && count <= w*h; y++)
        arr[w-i-1][y] = count++;

     // go left
     for (int x = w-2-i; x >= i && count <= w*h; x--)
        arr[x][h-i-1] = count++;

     // go up
     for (int y = h-2-i; y > i && count <= w*h; y--)
        arr[i][y] = count++;
  }

爪哇。

输出：

  1  2  3  4  5
 20 21 22 23  6
 19 32 33 24  7
 18 31 34 25  8
 17 30 35 26  9
 16 29 28 27 10
 15 14 13 12 11

Answer 2

对于每个单元格，有一个数字表示有多少空/已访问单元格处于其直接的垂直和水平位置（我们称之为numVisitedAroundCell）。此外，还有一个布尔标志isVisited。遍历单元格并更新numVisitedAroundCell（因此角落单元格将具有numVisitedAroundCell == 2并且不是角落的单元格的外层将具有numVisitedAroundCell == 1）

遍历单元格并找到一个角落单元格，这将是一个带有 的单元格numVisitedAroundCell == 2。

从那里开始，垂直或水平移动，同时标记您传递的每个单元格isVisited并增加numVisitedAroundCell. 继续沿着你选择的路径走，直到你碰到一个角落单元格（当你到达这个角落单元格时，numVisitedAroundCell应该是 3），然后找到下一个未访问的单元格，然后沿着那条路线走。如果你继续这样做，我相信你会得到你想要的螺旋。此外，这应该处理宽度均匀且大小不是正方形的情况。

Answer 3

递归地，没有充分的理由：

使用四个函数，命名为right()、down()、left()和up()。

该right()函数沿矩阵的第一行计数，然后将剩余的行（不包括刚刚填充的行）传递给 down().

该down()函数对矩阵的右边缘进行倒计时，然后将剩余的列传递给left()。

等等

当宽度或高度达到零时，递归停止。