迷宫问题 - 广度优先搜索(BFS)

2018-11-17

记录迷宫问题解法JavaScript实现

问题描述

给定一个迷宫，指明起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题（maze problem）

迷宫可以以二维数组来存储表示。0表示通路，1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示，均从0开始，给定起点（0,0）和终点（4,4），迷宫表示如下

const maze = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
]

广度优先搜索解法

const MAX_ROW = 5
const MAX_COL = 5

let head = 0 // 头指针
let tail = 0 // 尾指针

const queue = [] // visit队列

// 走过点的构造函数
function Point (row, col, predecessor) {
  this.row = row
  this.col = col
  this.predecessor = predecessor
}

// 进队，移动尾指针，添加点实例
function enQueue (point) {
  queue[tail++] = point
}

// 出队，移动头指针
function deQueue () {
  return queue[head++]
}

// 队列判空：头尾指针相等
function isEmpty () {
  return head === tail
}

// 迷宫地图
const maze = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
]


// 打印地图
function printMaze () {
  for (let i = 0; i < MAX_ROW; i++) {
    const printRow = []
    for (let j = 0; j < MAX_COL; j++) {
      printRow.push(maze[i][j])
    }
    console.log(printRow)
  }
  console.log('/************************/')
}

// 走一个点
function visit (row, col) {
  // predecessor设置为 head - 1，记录到达当前的头指针，用于路径回溯
  const point = new Point(row, col, head - 1)
  maze[row][col] = 6
  enQueue(point)
}

// 4个方向
const dirs = [
  [1, 0], [0, 1], [-1, 0], [0, -1]
]

// 入口函数
function main () {
  let p = new Point(0, 0, -1)
  maze[p.row][p.col] = 6
  enQueue(p)

  while (!isEmpty()) {
    p = deQueue()
    if (p.row === MAX_ROW - 1 && p.col === MAX_COL - 1) {
      break
    }
    for (let i = 0; i < dirs.length; i++) {
      const nexRow = p.row + dirs[i][0]
      const nexCol = p.col + dirs[i][1]
      if (
        nexRow >= 0 &&
        nexCol >= 0 &&
        nexRow < MAX_ROW &&
        nexCol < MAX_COL &&
        maze[nexRow][nexCol] == 0
      ) {
        visit(nexRow, nexCol)
      }
    }
    printMaze()
  }

  if (p.row === MAX_ROW - 1 && p.col === MAX_COL - 1) {
    console.log(p.row, p.col)
    while (p.predecessor !== -1) {
      p = queue[p.predecessor]
      console.log(p.row, p.col)
    }
  } else {
    console.log('No path!')
  }
}

main()

输出结果如下

[ 6, 1, 0, 0, 0 ]
[ 6, 1, 0, 1, 0 ]
[ 0, 0, 0, 0, 0 ]
[ 0, 1, 1, 1, 0 ]
[ 0, 0, 0, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 0, 1, 0 ]
[ 6, 0, 0, 0, 0 ]
[ 0, 1, 1, 1, 0 ]
[ 0, 0, 0, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 0, 1, 0 ]
[ 6, 6, 0, 0, 0 ]
[ 6, 1, 1, 1, 0 ]
[ 0, 0, 0, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 0, 1, 0 ]
[ 6, 6, 0, 0, 0 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 0, 0, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 0, 1, 0 ]
[ 6, 6, 6, 0, 0 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 0, 0, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 0, 1, 0 ]
[ 6, 6, 6, 0, 0 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 6, 0, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 6, 1, 0 ]
[ 6, 6, 6, 6, 0 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 6, 0, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 6, 1, 0 ]
[ 6, 6, 6, 6, 0 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 6, 6, 1, 0 ]
/************************/
[ 6, 1, 0, 0, 0 ]
[ 6, 1, 6, 1, 0 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 6, 6, 1, 0 ]
/************************/
[ 6, 1, 6, 0, 0 ]
[ 6, 1, 6, 1, 0 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 6, 6, 1, 0 ]
/************************/
[ 6, 1, 6, 0, 0 ]
[ 6, 1, 6, 1, 0 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 0 ]
[ 6, 6, 6, 1, 0 ]
/************************/
[ 6, 1, 6, 0, 0 ]
[ 6, 1, 6, 1, 6 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 6 ]
[ 6, 6, 6, 1, 0 ]
/************************/
[ 6, 1, 6, 6, 0 ]
[ 6, 1, 6, 1, 6 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 6 ]
[ 6, 6, 6, 1, 0 ]
/************************/
[ 6, 1, 6, 6, 0 ]
[ 6, 1, 6, 1, 6 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 6 ]
[ 6, 6, 6, 1, 6 ]
/************************/
[ 6, 1, 6, 6, 6 ]
[ 6, 1, 6, 1, 6 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 6 ]
[ 6, 6, 6, 1, 6 ]
/************************/
[ 6, 1, 6, 6, 6 ]
[ 6, 1, 6, 1, 6 ]
[ 6, 6, 6, 6, 6 ]
[ 6, 1, 1, 1, 6 ]
[ 6, 6, 6, 1, 6 ]
/************************/
4 4
3 4
2 4
2 3
2 2
2 1
2 0
1 0
0 0