javascript – 5×5网格中所有可能的移动？

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

如何计算所有可能的路径,而不使用相同的方格两次,一个人可以从s到e？

我创建了一个网格数组[[1,1] … [5,5]],但我不知道这是否有效.

我还绘制了可能的方块,并试图创建一个记录和检查和大量的垃圾.

我可以在这里使用任何标准配方吗？

解决方法:

您可以使用相当多的标准路径寻找算法.

这与javascript无关.

你可以使用一个没有启发式的algorhythm,你不应该停止第一个解决方案.

以下是如何做到这一点：

诀窍是你需要将已经访问的方块存储在一个列表中,并检查你是否在每一步都重新访问其中一个方块.

另一个技巧是你需要相邻方块之间的明确顺序. (像顶部/右侧/底部/左侧.这是一个非常愚蠢的算法,但对于这种特殊情况很好.)

你还需要能够识别正方形(它的位置是可能的)

考虑一个递归函数(例如将其命名为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中得到你的结果,这是一个有希望的路径列表.

此外,它只有一半的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个进球.还有人应检查我的代码是否正确.

来源：http://www./content-1-217851.html