หาระยะห่างจาก 0 ใกล้ที่สุดในเมทริกซ์ไบนารี (Binary Matrix) ด้วย JavaScript

ปัญหา

ได้รับเมทริกซ์ไบนารี (มีแค่ 0 และ 1) ให้สร้างเมทริกซ์ใหม่ขนาดเดียวกัน โดยแต่ละเซลล์เก็บระยะห่างไปยัง 0 ใกล้ที่สุด (เคลื่อนที่ได้เฉพาะแนวนอน/แนวตั้ง)

ตัวอย่าง

const arr = [[0,0,0],[0,1,0],[1,1,1]];

ผลลัพธ์: [[0,0,0],[0,1,0],[1,2,1]]

โค้ดตัวอย่าง (BFS Multi-source)

const arr = [[0,0,0],[0,1,0],[1,1,1]]; 
const findNearestDistance = (arr = []) => { 
  let array = []; 
  let res = arr.map((el, ind) => el.map((subEl, subInd) => { 
    if (subEl === 0) { array.push([ind, subInd]); return 0; } 
    return Number.MAX_SAFE_INTEGER; 
  })); 
  const updateAdjacent = (ind, subInd, min, array = []) => { 
    if (ind < 0 || subInd < 0 || ind == arr.length || subInd == arr[0].length) return; 
    if (res[ind][subInd] < min + 2) return; 
    res[ind][subInd] = min + 1; 
    array.push([ind, subInd]); 
  }; 
  while (array.length) { 
    let next = []; 
    for (let [ind, subInd] of array) { 
      updateAdjacent(ind, subInd + 1, res[ind][subInd], next); 
      updateAdjacent(ind, subInd - 1, res[ind][subInd], next); 
      updateAdjacent(ind + 1, subInd, res[ind][subInd], next); 
      updateAdjacent(ind - 1, subInd, res[ind][subInd], next); 
    } 
    array = next; 
  } 
  return res; 
}; 
console.log(findNearestDistance(arr));

ผลลัพธ์

[ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 1, 2, 1 ] ]