s o o o o
o o o o o
o o o o o
o o o o o
o o o o e

如何計(jì)算所有可能的路徑,而不使用相同的方格兩次,一個人可以從s到e？

我創(chuàng)建了一個網(wǎng)格數(shù)組[[1,1] … [5,5]],但我不知道這是否有效.

我還繪制了可能的方塊,并試圖創(chuàng)建一個記錄和檢查和大量的垃圾.

我可以在這里使用任何標(biāo)準(zhǔn)配方嗎？

解決方法:

您可以使用相當(dāng)多的標(biāo)準(zhǔn)路徑尋找算法.

這與javascript無關(guān).

你可以使用一個沒有啟發(fā)式的algorhythm,你不應(yīng)該停止第一個解決方案.

以下是如何做到這一點(diǎn)：

訣竅是你需要將已經(jīng)訪問的方塊存儲在一個列表中,并檢查你是否在每一步都重新訪問其中一個方塊.

另一個技巧是你需要相鄰方塊之間的明確順序. (像頂部/右側(cè)/底部/左側(cè).這是一個非常愚蠢的算法,但對于這種特殊情況很好.)

你還需要能夠識別正方形(它的位置是可能的)

考慮一個遞歸函數(shù)(例如將其命名為Visit)：

function visit(square) {

    add the square to the pathlist //pathlist is not a list of paths but a list of squares which is the current path

    if (square is the goal) {
        add a copy of the pathlist to the goalslist
    }
    else {
        for (each adjacency in square.adjacencies) { // this can be calculated by adding  1 and -1 to the coordinates, and checking if its overflowing (less then one/more than five)
            if (adjacency is in pathlist) {
                //do nothing we have already been here
            }
            else {
                visit(adjacency)
            }
        }
    }

    remove square from the pathlist!!
}

通過訪問(開始)開始這個algorythm.你可以在goallist中得到你的結(jié)果,這是一個有希望的路徑列表.

此外,它只有一半的javascript-half偽代碼,但很容易從中編寫javascript.

編輯：享受解決方案：

<script type="text/javascript">
var start = [1,1],
    goal = [5,5],
    pathList = [],
    solutionList = [],
    solutionCount = 0,
    width = 5,
    height = 5;


function squareInArray(square, array) {
    var i = 0,
        x = square[0], 
        y = square[1];

    for (i = 0; i < array.length; i  ) {
        if (x == array[i][0] && y == array[i][1]) {
            return true;
        }
    }
    return false;
}


function visit(square) {
    var i = 0,
        x = square[0], 
        y = square[1],
        adjacencies = [[x-1,y],[x 1,y],[x,y 1],[x,y-1]];

    pathList.push(square);

    if (x == goal[0] && y == goal[1]) {
        var solution = pathList.slice(0); //copy trick
        solutionList.push(solution);
        solutionCount  ;
        //alert(solution);
    }
    else {
        for (i = 0; i < adjacencies.length; i  ) {
            if (adjacencies[i][0] < 1 || adjacencies[i][0] > width || adjacencies[i][1] < 1 ||adjacencies[i][1] > height) {
                //overflow
            }
            else {
                if (squareInArray(adjacencies[i], pathList)) {
                    //do nothing we have already been here
                }
                else {
                    visit(adjacencies[i]);
                }
            }
        }
    }

    pathList.pop();
}

visit(start);

alert(solutionCount);
</script>

8512個進(jìn)球.還有人應(yīng)檢查我的代碼是否正確.