广度优先搜索

概念

广度优先搜索（Bread First Search: BFS）对源节点的子结点都进行遍历后，才会遍历子结点的子结点。BFS是很多重要的图算法的原型，比如Prim最小生成树算法和Dijkstra单源最短路径算法。

LeetCode之广度优先搜索

505.The Maze II
设定与迷宫I一致，0表示空格，1表示障碍物，四周为墙；球一旦滚动则一直到遇到墙为止。求到达终点的最短距离。

由于这道题需要计算起点到终点最短路径，Dijkstra单源最短路径算法可解。用优先队列来存储每次要遍历的结点。

var PriorityQueue = require('./PriorityQueue');

var Point = function (x, y, l, p) {
  this.x = x;
  this.y = y;
  this.l = l;
};

var shortestDistance = function (maze, start, dest) {
  if (maze.length == 0 || maze[0].length == 0) return false;
  if (start[0] == dest[0] && start[1] == dest[1]) return true;
  //init points
  var points = [];
  for (var i = 0; i < maze.length; i++) {
    points.push([]);
    for (var j = 0; j < maze[0].length; j++) {
      points[i].push(new Point(i, j, Number.MAX_VALUE));
    }
  }
  //priority queue to BFS
  var queue = new PriorityQueue(function compare(node1, node2) {
    return node1.l > node2.l;
  });
  //init the start
  queue.push(new Point(start[0], start[1], 0));
  var ds = "dlru";
  var dir = [[1, 0], [0, -1], [0, 1], [-1, 0]];
  while (queue.size() > 0) {
    var node = queue.pop();
    if (!queue.comparator(points[node.x][node.y], node)) continue;
    points[node.x][node.y] = node;
    for (i = 0; i < dir.length; i++) {
      var x = node.x, y = node.y, l = node.l, p = node.p;
      if (notWall(maze, x + dir[i][0], y + dir[i][1])) {
        while (notWall(maze, x + dir[i][0], y + dir[i][1])) {
          x += dir[i][0];
          y += dir[i][1];
          l++;
        }
        queue.push(new Point(x, y, l));
      }
    }
  }
  return points[dest[0]][dest[1]].l == Number.MAX_VALUE ? -1 : points[dest[0]][dest[1]].l;
};

499.The Maze III
这次迷宫中有一个洞，如果球滚到洞里就停止，其余与The Maze I一致，求到洞的最短距离中的最小（词典序）路径。

其实与The Maze II解法相同，只不过在点的类型中加入路径属性作为比较的附属

var PriorityQueue = require('./PriorityQueue');

var Point = function (x, y, l, p) {
  this.x = x;
  this.y = y;
  this.l = l;
  this.p = p;
};

var reachPath = function (maze, ball, hole) {
  if (maze.length == 0 || maze[0].length == 0) return false;
  if (ball[0] == hole[0] && ball[1] == hole[1]) return true;
  //init points
  var points = [];
  for (var i = 0; i < maze.length; i++) {
    points.push([]);
    for (var j = 0; j < maze[0].length; j++) {
      points[i].push(new Point(i, j, Number.MAX_VALUE, ""));
    }
  }
  //priority queue to BFS
  var queue = new PriorityQueue(function compare(node1, node2) {
    return node1.l > node2.l ? true : (node1.l < node2.l ? false : node1.p > node2.p);
  });
  //init the start
  queue.push(new Point(ball[0], ball[1], 0, ""));
  var ds = "dlru";
  var dir = [[1, 0], [0, -1], [0, 1], [-1, 0]];
  while (queue.size() > 0) {
    var node = queue.pop();
    if (!queue.comparator(points[node.x][node.y], node)) continue;
    points[node.x][node.y] = node;
    for (i = 0; i < dir.length; i++) {
      var x = node.x, y = node.y, l = node.l, p = node.p;
      if (notWall(maze, x + dir[i][0], y + dir[i][1])) {
        while (notWall(maze, x + dir[i][0], y + dir[i][1])) {
          x += dir[i][0];
          y += dir[i][1];
          l++;
          if (x == hole[0] && y == hole[1]) {
            break;
          }
        }
        queue.push(new Point(x, y, l, p + ds[i]));
      }
    }
  }
  return points[hole[0]][hole[1]].l == Number.MAX_VALUE ? "impossible" : points[hole[0]][hole[1]].p;
};

317.Shortest Distance from All Buildings
二维地图中，1表示建筑物，2表示障碍物，0表示空地。返回距离地图中所有建筑物最近的距离和。

Input: 
 1 - 0 - 2 - 0 - 1
 |   |   |   |   |
 0 - 0 - 0 - 0 - 0
 |   |   |   |   |
 0 - 0 - 1 - 0 - 0
Output: 7

对于每个建筑物，用BFS来搜索到每个点的最短距离；对每次求出的距离求和，最后对所有的总距离求最小值。

//BFS: from every building and add the shortest distance
var shortestPosition = function (grid) {
  if(!grid || !grid.length || !grid[0].length) return -1;
  //init dis matrix
  var minDis=Number.MAX_VALUE,row =grid.length,col=grid[0].length;
  var totalDist=[],dist=[];
  for(var i=0;i<row;i++) {
    totalDist.push(new Array(col).fill(0));
    dist.push(new Array(col).fill(Number.MAX_VALUE));
  }
  //BFS and iterate
  for(i=0;i<row;i++) {
    for(var j=0;j<col;j++) {
      if(grid[i][j]==1) {
        BFS(grid,dist,i,j);
        console.log("dist:",dist);
        minDis = findMinDist(totalDist,dist);
        console.log("totalDist:",totalDist);
      }
    }
  }
  return minDis==Number.MAX_VALUE?-1:minDis;
};

function BFS(grid,dist,x,y) {
  for(var i=0;i<grid.length;i++) {
    for(var j=0;j<grid[0].length;j++) {
      dist[i][j]=Number.MAX_VALUE;
    }
  }
  var queue=[];
  queue.push([x,y]);
  dist[x][y]=0;
  while(queue.length>0) {
    var node=queue.shift();
    var dir=[[0,-1],[1,0],[0,1],[-1,0]];
    for(i=0;i<dir.length;i++) {
      var x=node[0],y=node[1];
      if(isValidPoint(grid,x+dir[i][0],y+dir[i][1]) &&
        dist[x+dir[i][0]][y+dir[i][1]]>dist[x][y]+1) {
        dist[x+dir[i][0]][y+dir[i][1]]=dist[x][y]+1;
        queue.push([x+dir[i][0],y+dir[i][1]]);
      }
    }
  }
}

function findMinDist(totalDist,dist) {
  var min=Number.MAX_VALUE;
  for(var i=0;i<totalDist.length;i++) {
    for(var j=0;j<totalDist[0].length;j++) {
      if(dist[i][j]==Number.MAX_VALUE) {
        totalDist[i][j]=Number.MAX_VALUE;
      } else {
        totalDist[i][j]=totalDist[i][j]+dist[i][j];
      }
      min=Math.min(min,totalDist[i][j]);
    }
  }
  return min;
}

function isValidPoint(grid,x,y) {
  return x>-1 && x<grid.length && y>-1 && y<grid[0].length && grid[x][y]!=2;
}