题目

给定二维数组中两个元素
找出连通两个元素的最短路径

测试用例

// 给定数组 0可以通行 1不可以通行
var origin = [
            [0,0,1,0],
            [0,0,1,0],
            [0,0,1,0],
            [0,0,0,0]
        ];

var start = [0,0];

var end = [0,3];

代码

var origin = [
    [0,0,1,0,0],
    [0,0,1,0,1],
    [0,0,1,0,0],
    [0,0,0,0,1]
];

// 起始点
var start = [1,1];
// 终止点
var end = [2,4];

// 起始过的点集合
var visited = [];
// 走过的路径集合
var prev = [];

/*迷宫走路*/
function search(a,b) {
    var queue = [];
    queue.push(a);

    var result = null;
    visited.push(a);
    prev.push({
        x: a[0],
        y: a[1],
        prev: null
    });

    while (queue.length > 0){
        var item = queue.splice(0,1);
        item = item[0];

        if(origin[item[0]][item[1]] == 1){
            continue;
        }
        
        if(item[0] == end[0] && item[1] == end[1]) {
            break;
        }

        var left = {
            x: item[0] - 1,
            y: item[1]
        };
        var right = {
            x: item[0] + 1,
            y: item[1]
        };
        var top = {
            x: item[0],
            y: item[1] - 1
        };
        var bottom = {
            x: item[0],
            y: item[1] + 1
        };

        var direction = [];
        direction.push(left);
        direction.push(right);
        direction.push(top);
        direction.push(bottom);
        
        var maxX = origin.length;
        var maxY = origin[0].length;
        $isbreak = false;
        for(var len = direction.length , i = len - 1 ; i >= 0 ; --i ){
            if(direction[i].x >= 0 && direction[i].x < maxX && direction[i].y >= 0 && direction[i].y < maxY){//坐标未溢出
                if(!checkVisited(direction[i])){
                    visited.push([direction[i].x,direction[i].y]);

                    var obj = {
                        x: direction[i].x,
                        y: direction[i].y,
                        prev: null
                    }

                    for(var l = prev.length , j = l - 1; j >= 0 ; --j){
                        if(prev[j].x == item[0] && prev[j].y == item[1]){
                            obj.prev = prev[j];
                            break;
                        }
                    }

                    prev.push(obj);
                    
                    if(obj.x == end[0] && obj.y == end[1]) {
                        $isbreak = true;
                        break;
                    }
                    
                    queue.push([direction[i].x,direction[i].y]);
                }

            }
        }
        if ($isbreak) break;
    }

}

function checkVisited(obj) {
    for(var l = visited.length , j = l - 1 ; j >= 0 ; --j){
        if(obj.x == visited[j][0] && obj.y == visited[j][1]){
            return true;
        }
    }

    return false;
}

var r = search(start,end);

// 输出走过的最短路径
function checkPrev(p) {
    while (p.prev){
        console.log(p.x,p.y);
        p = p.prev;
    }

    console.log(p.x,p.y);
}

checkPrev(prev[prev.length - 1]);

验证

checkPrev(prev[prev.length - 1]);