c# - 在二维数组中寻找循环

Question

嗨，我想在二维（nxm）数组中找到循环。我的数组中有 nm-1 个填充单元格，我想找到循环开始空单元格，在填充单元格中继续，在空单元格中完成。

例如我们有这个数组；

我们的第一个周期是 [0,0],[0,3],[2,3],[2,0] 第二个周期是 [0,1],[0,3],[2,3],[2 ,2],[3,2],[3,1]

我怎样才能找到这个数组中的所有循环。

谢谢。

Answer 1

我想我有一个算法可以满足你的需要。

第一步是找到所有起点（这很容易），用您所在的点初始化一条路径，然后尝试从该点向左、向右、向上或向下移动。

    public void start() {
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                if (array[y][x] == 0) {
                    int pos[] = {x,y};
                    path = new ArrayList<int[]>();
                    path.add(pos);
                    startx = x;
                    starty = y;
                    follow(x, y, 1, 0);
                    follow(x, y, -1, 0);
                    follow(x, y, 0, 1);
                    follow(x, y, 0, -1);
                }
            }
        }
    }

一旦您开始沿着特定方向的路线行驶，如果您再次到达起点，您就找到了一个循环，因此您无法输出到达那里的路径并放弃沿该路线的任何进一步搜索。

如果您发现一个非空单元格，您需要将您当前的位置添加到您的路径历史中，然后尝试递归地沿着与您所在方向成直角的另一条路线。因此，如果您要向左或向右，您现在只尝试向上或向下，反之亦然。

如果您的路线带您越过边缘而没有找到您的起点或非空单元格，那么您显然无法继续前进。

    private void follow(int x, int y, int dx, int dy) {
        x += dx;
        y += dy;
        while (x >= 0 && x < w && y >= 0 && y < h) {
            if (x == startx && y == starty) {
                for (int[] pos : path) {
                    System.out.printf("[%d,%d] ",pos[1], pos[0]);
                }
                System.out.printf("\n");
                break;
            }
            if (array[y][x] != 0) {
                int pos[] = {x,y};
                path.add(pos);
                if (dx != 0) {
                    follow(x, y, 0, 1);
                    follow(x, y, 0, -1);
                }
                else {
                    follow(x, y, 1, 0);
                    follow(x, y, -1, 0);
                }
                path.remove(path.size()-1);
            }
            x += dx;
            y += dy;
        }
    }

这是关于 ideone 的完整工作示例

我注意到这个算法有几个问题可能不适合你，具体取决于你的要求。

1. 你实际上得到了每条路径的两个版本 - 一个遵循顺时针路线，另一个显然是逆时针。
2. 一些路径跨越自己的路线。例如，类似于八字形图案的东西。我不知道这是否是您会接受的有效循环。