在 O(1) 时间内检查随机更新矩阵的第一行和最后一行之间的路径

Question

我们从一个充满 0 的 nxn 矩阵开始。每次迭代后，都会选择矩阵的随机单元并将其更改为 1。如果再次选择已经更改的单元，它将保持为 1，然后我们继续选择一个新的随机单元。

目标是在每次迭代后确定在 O(1) 时间内是否存在连接矩阵第一行和最后一行的路径。

我们定义一条路径由一组1的邻居单元组成。如果两个单元格彼此相距至多 1 平方且都包含 1，则它们是邻居。例如，第 (i,j) 个单元格可能具有以下坐标作为其邻居单元格：(i-1, j -1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i +1，j）和（i+1，j+1）。换句话说，只有包围它的细胞才可能成为它的邻居并开始与它形成路径。

我知道有一些算法可以为固定矩阵找到这样的路径，但它们至少需要 O(n^2) 时间。为了实现 O(1) 时间，我必须使用之前迭代中的信息，但到目前为止，我仅通过递归遍历最后更改的单元格的所有可能路径来实现 O(n) 时间。

我相信使用高效的数据结构适合实现所需的 O(1) 时间，但我对此不太熟悉。

如果有人可以草拟一个有效的算法来实现此目的或以某种方式指导我，我将非常感激。

提前谢谢您。

Answer 1

除了保存单元格是“0”还是“1”之外，还添加有关是否存在从开始到该单元格的路径的信息。然后，当添加新单元格时，您将更新所有要访问的潜在新邻居。虽然这样的更新在最坏的情况下可能是 O(n)（其中

n

是“1”的元素数量），但它将摊销 O(1)，因为每个单元格仅以这种方式更新一次。

record Cell(boolean active, boolean hasPath){}

private Cell[][] field = createEmptyField();

private Cell[][] createEmptyField(int n){
    Cell[][] field = new Cell[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            field[i][j]=new Cell(false, false);
        }
    }
    return field;
}

public void fillInRandomlyUntilPath(int startX, int startY, int endX, int endY){
    Random random = ThreadLocalRandom.current();
    while(!field[endX][endY].hasPath()){
        int selectedX = random.nextInt(field.length);
        int selectedY = random.nextInt(field[selectedX].length);
        if(!field[selectedX][selectedY].active()){
            field[selectedX][selectedY] = new Cell(true, false);
            forAllNeighbours(selectedX, selectedY, (x,y)->{
                if(field[x][y].hasPath()){
                    setPath(selectedX, selectedY);
                }
            });
        }
    }
}
private void setPath(int x,int y){
    if(!field[x][y].hasPath()){
        field[x][y]=new Cell(true, true);
    }
    forAllNeighbours(x,y,(newX, newY) -> setPath(newX, newY));
}
//execute a function for all neighbours of a point
private void forAllNeighbours(int x, int y, BiConsumer<Integer, Integer> exec){
    for(int i=Math.max(0,x-1);i<Math.min(field.length,x+1);i++){
        for(int j=Math.max(0,y-1);j<Math.min(field[i].length,y+1);i++){
            if(x!=i||y!=j){
                exec.accept(i,j);
            }
        }
    }
}