5x5网格中所有可能的移动？

Question

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]],但我不知道这是否有效.

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

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

Answer 1

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

这与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://jsfiddle.net/SoonDead/rd2GN/3/