jas0nhuang

[筆記] 再走一次迷宮

再試一次自已把走迷宮寫出來，然後一步一步記錄想法，建議沒有自已想過，或者沒有看著老師的解法仔細想過的同學先不要看。
然後我把所有自已測試時用到的 console.log() 都留下來了，當作一個思考過程的記錄

solve([
  '3 3', // 迷宮高與寬（先高、後寬）
  '...', // 迷宮圖樣
  '...',
  '...'
])

function solve(lines) {
  // 將高、寬轉換為數字存入陣列
  const HWArray = lines[0].split(' ')
  // console.log(HWArray)
  // 分別取出高 H、寬 W
  const H = Number(HWArray[0])
  const W = Number(HWArray[1])
  // 將迷宮存入陣列
  const maze = []
  for (let i = 1; i < lines.length; i++) {
    maze.push(lines[i])
  }
  // console.log(maze)
  // 計算出終點
  const endX = H - 1
  const endY = W - 1

  // 設定一個空陣列等一下用來儲存走到每個點的步數
  let stepsArr = []
  // 先在這個空陣列裡面填入與高度同數量的空陣列
  for (let i = 1; i < H + 1; i++) {
    stepsArr.push([ ])
  }
  // 設定起點（0, 0）到起點的步數為 0
  stepsArr[0][0] = 0

  // 設定一個列隊，用來存入可以走的點，起始設定為起點： 0, 0
  let pointQueue = [{x:0, y:0}]

  // 設定一個向四個方向走的陣列
  const directions = [
    { "dx": 0, "dy": 1},
    { "dx": 1, "dy": 0},
    { "dx": 0, "dy": -1},
    { "dx": -1, "dy": 0}
  ]
  
  // 開始走迷宮
  // 只要列隊中還有未走過的點就執行以下運算
  while (pointQueue.length) {
    // 先取出目前所在的點，然後從 pointQueue 列隊中刪除
    let currentPoint = pointQueue.shift()
    let x = currentPoint.x
    let y = currentPoint.y
    // console.log(x, y)
    // 往四個方向走，進行判斷
    for (let i = 0; i < directions.length; i++) {
      // console.log(directions[i].dx)
      let newX = x + directions[i].dx
      let newY = y + directions[i].dy
      // 判斷條件：
      // 超過邊界或者路不能走
      if (newX < 0 || newY < 0 || newX > endX || newY > endY || maze[newX][newY] !== '.') continue
      // 要走的點的步數大於原始點加上 1 步或者不是未走過的路
      if (stepsArr[newX][newY] <= stepsArr[x][y] + 1 || stepsArr[newX][newY] !== undefined) continue
      // 通過以上判斷則為要走的點。
      // 將到達原始點的步數加上 1 步，放入儲存步數的陣列中 stepsArr[newX][newY]
      stepsArr[newX][newY] = stepsArr[x][y] + 1
      // 將可以走的點加入列隊，等待成為之後的起始點。（列隊中可以同時有好幾個點）
      pointQueue.push({x:newX, y:newY})
      // console.log(pointQueue)
      // console.log(`newX and newY: ${newX} : ${newY}`)
    }
  }
  // console.log(stepsArr)
  console.log(stepsArr[endX][endY])
}

其實就是把老師的解法從自已的記憶裡挖出來然後寫出來這樣。

其中有一個地方很神奇，就是最後在判斷是否為未走過的點以及原始點（老師說的 A 點）到前往點（老師說的 B 點）的距離比較那裡。
我第一次不知道腦子進了什麼東西，寫出來變這樣，明顯就是錯誤（不相關）的判斷：

if (stepsArr[newX][newY] > stepsArr[x][y] + stepsArr[newX][newY] || stepsArr[newX][newY] !== undefined) continue

但是居然 AC！
仔細又看了一次老師的解法，發現好像沒有去判斷 A 走到 B 點的距離也沒關係，所以就試著把那一部分刪了，變成：

if (stepsArr[newX][newY] !== undefined) continue

也還是 AC。XD
我自已的感覺是，其實只要判斷是否有走過就可以了？！或者是測資還不夠強，遇到更複雜的迷宮就可能會算錯？！