LIOJ — 1053

Photo by James Harrison on Unsplash

希望藉由程式解題的過程重新打好程式基礎和學習遺漏的相關知識點

會將解題過程遇到困難的地方做個紀錄

測驗網站：LidemyOJ ( LIOJ ) by 胡立 ( Huli )

免費課程 — [ALG101] 先別急著寫 leetcode by 胡立 ( Huli )

討論區：Lidemy Discussions by 胡立 ( Huli )

這題 Level ( Medium ) 有提示可以搜尋 “BFS”

🔖 文章索引

1. 參考文章
2. 實作方法
3. 測試資料
4. 程式碼
5. 延伸閱讀

參考文章

廣度優先搜尋 - 維基百科，自由的百科全書

DFS與BFS - HackMD

實作方法

1. 首先將［根節點］放入佇列中
2. 從佇列中取出第一個節點，並檢驗它是否為終點

● 如果是終點，則結束並回傳走了幾步

● 否則將它依照方向［上、下、左、右］驗證通過的直接將［子節點］加入佇列中

驗證內容不能超過迷宮的寬、高 且 大於 0 且 還未走過 且 為通道 .

測試資料

3 4
.#..
....
....

Ans: 5

6 8
......##
#.#.#...
..###.#.
.##.....
....##.#
#.#.....

Ans: 12

9 18
...##########....#
##........###.##.#
#########.###.##.#
...#...##.###.##.#
.#.#.#.##.###.##.#
.#...#....###.##.#
.############.##.#
..............##.#
################..

Ans: 65

程式碼

小地雷 — 賦值時 a++、++a 的差別

當節點嘗試往［右、左、下、上］經過驗證通過後需要 let tempStep = current.step; ，將當前的步數存在一個變數來做後續的使用。

如果沒有這樣做而是直接 let _step = ++current.step;

可以打開 // log(QUEUE); 觀察變化

會發現明明是走 2步的節點變成 3步了 😱

var readline = require('readline');

var lines = []
var rl = readline.createInterface({
  input: process.stdin
});

rl.on('line', function (line) {
  lines.push(line)
});

rl.on('close', function() {
  solve(lines)
})

const log = console.log;

function solve(lines) {
  const TEMP = lines[0].split(' ').map(Number);
  const HEIGHT = TEMP[0];
  const WIDTH = TEMP[1];

  const MATRIX = [];
  const VISITED = new Array(HEIGHT).fill('').map(() => new Array(WIDTH).fill(false));
  const DIRECTIONS = [ [0, 1], [0, -1], [1, 0], [-1, 0] ];
  
  const QUEUE = [];

  QUEUE.push({
    x: 0,
    y: 0,
    path: '0, 0',
    step: 0
  })
  VISITED[0][0] = true;

  const END = [HEIGHT - 1, WIDTH - 1];

  for (let i = 1; i <= HEIGHT; i++) {
    let tempArray = [];

    for (let j = 0; j < WIDTH; j++) {
      tempArray.push(lines[i][j]);
    }

    MATRIX.push(tempArray);
  }

  while(QUEUE.length) {
    // log(QUEUE);
    let current = QUEUE.shift();

    if (current.x === END[0] && current.y === END[1]) {
      log(current.step);
      break;
    }

    // 節點嘗試往［右、左、下、上］
    for (let dir of DIRECTIONS) {
      let nextY = current.x + dir[0];
      let nextX = current.y + dir[1];
  
      if (
        nextY < HEIGHT &&
        nextY >= 0 &&
        nextX < WIDTH &&
        nextX >= 0 &&
        MATRIX[nextY][nextX] === '.' &&
        VISITED[nextY][nextX] === false
      ) {
        let tempStep = current.step;
        let _path = `${current.path} => ${nextY}, ${nextX}`;
        let _step = ++tempStep;

        QUEUE.push({
          x: nextY,
          y: nextX,
          path: _path,
          step: _step
        });

        VISITED[nextY][nextX] = true;
      }
    }
  }
}

延伸閱讀

• LIOJ — 1004
• LIOJ — 1019
• LIOJ — 1052