如何找到渗透路径并突出显示？

Question

我使用快速合并算法来查找前五个站点中是否有一个与后五个站点之一相连。

前五个站点具有相同的根，即倒数第二个数组元素。后五个站点也具有相同的根，即最后一个数组元素。

for (let i = 0; i < 5; i++) {
        this.union(i,this.array.length-2);
    }
    for (let j = this.array.length-this.number-2; j < this.array.length-2; j++) {
        this.union(j,this.array.length-1);
    }

我需要画出这样的路径：

我用于突出显示网站的代码如下：

let id =   this.array[this.array.length-2]
for (let i = 0; i < this.array.length-2; i++) {
    if(this.connected(i,id) && $("#result td").eq(i).hasClass('opened')){
        $("#result td").eq(i).css({'background':'blue'});
    }

}

结果如下： 但是，左侧两个网站被突出显示并不正确。 我应该使用什么算法来仅突出显示正确的路径？

连接方法：

connected(p, q){
    return this.root(p) === this.root(q);
}

根权限方法

root(index){
    while(this.array[index] !== index) index = this.array[index];
    return index;
}

- dr Anton

---

“正确路径”是什么意思？是指从起点到终点的路径吗？ - zenwraight

基本上，您不希望所有未阻塞的路径都被渗透，对吧？ - zenwraight

如果我们填满与顶部行相连的所有开放站点，并且该过程填充底部行上的一些开放站点，则系统渗透。 - dr Anton

开放的站点对应着水可能流过的空位，因此一个渗透系统会让水填满这些开放的站点，从上往下流动。 - dr Anton

如果你只想突出显示从顶部到底部行之间的最短路径，请查找寻路算法，你只需要跟踪以前的状态（BFS就足够了）。如果你想突出显示连接顶部和底部行的整个区域，请使用泛洪填充。 - c2huc2hu

Answer 1

看起来你只需要一个基本的填充算法，但有两个注意事项。1）你只想让它向下填充，就像水流一样。2）你希望在第一行（顶部）的每个空白处都调用Fill()，就像水从顶部倾泻而下。

var EMPTY = 0; // empty unfilled spot
var SOLID = 1; // solid spot
var FILLED = 2; // filled spot
var ROWS = 5; // # of rows of data indexed 0 to 4
var COLS = 5; // # of columns of data indexed 0 to 4
var data = [
    [1,0,0,1,1],
    [1,1,0,1,1],
    [0,1,0,0,1],
    [0,1,1,0,1],
    [0,1,1,0,1]
]; // data that matches the example

// check if a location is EMPTY
function isEmpty(grid, rowIndex, colIndex) {
    // valid row and col?
    if(rowIndex < 0 || rowIndex >= ROWS || colIndex < 0 || colIndex >= COLS) {
        return false;
    }
    // SOLID or FILLED already?
    if(grid[rowIndex][colIndex] !== EMPTY) {
        return false;
    }
    return true;
}

// replace EMPTY locations with FILLED locations
function fillDown(grid, startRow, startCol) {
    if(false === isEmpty(grid, startRow, startCol)) {
        return;
    }
    var nextLocation = [[startRow, startCol]]; // list of locations to process
    while(nextLocation.length > 0) { // loop
        var loc = nextLocation.pop();
        var r = loc[0]; // row index
        var c = loc[1]; // column index
        // fill the empty location
        grid[r][c] = FILLED;
        // try to fill the locations to the LEFT, RIGHT and DOWN from the current location
        if(isEmpty(grid, r, c - 1)) { // left
            nextLocation.push([r, c - 1]);
        }
        if(isEmpty(grid, r, c + 1)) { // right
            nextLocation.push([r, c + 1]);
        }
        if(isEmpty(grid, r + 1, c)) { // down
            nextLocation.push([r + 1, c]);
        }
    }
}

// call fillDown() for the first row of the data (water pouring accross the top)
for(var c = 0; c < COLS; c++) {
    fillDown(data, 0, c);
}

// show the result
alert(data.join('\n'));

额外说明，二维数组的行和列索引可以通过公式进行转换，即：index = (r * COLS) + c，因此数据行中最后一个位置（row=4，col=4）的索引为 4 * 5 + 4 == 24，是一维数组中最后一个位置的索引。

- Louis Ricci