ปัญหาอัลกอริทึม - รูปแบบการย้อนรอยใน JavaScript

พิจารณาปัญหาการย้อนรอยต่อไปนี้ บนตาราง 2 มิติ มีสี่เหลี่ยม 4 ประเภท −

• 1 หมายถึงกำลังสองเริ่มต้น มีสี่เหลี่ยมเริ่มต้นเพียงหนึ่งช่อง

• 2 หมายถึงช่องสี่เหลี่ยมสิ้นสุด มีสี่เหลี่ยมจัตุรัสสิ้นสุดเพียงช่องเดียว

• 0 หมายถึงช่องสี่เหลี่ยมเปล่าที่เราเดินผ่านได้

• -1 คือสิ่งกีดขวางที่เราเดินผ่านไม่ได้

เราจำเป็นต้องเขียนฟังก์ชันที่คืนค่าจำนวนการเดิน 4 ทิศทางจากจัตุรัสเริ่มต้นไปยังจัตุรัสสิ้นสุด ซึ่งเดินข้ามทุกช่องสี่เหลี่ยมที่ไม่ใช่สิ่งกีดขวางเพียงครั้งเดียว

ตัวอย่าง

const arr = [
   [1,0,0,0],
   [0,0,0,0],
   [0,0,2,-1]
];
const uniquePaths = (arr, count = 0) => {
   const dy = [1,−1,0,0], dx = [0,0,1,−1];
   const m = arr.length, n = arr[0].length;
   const totalZeroes = arr.map(row => row.filter(num => num ===
   0).length).reduce((totalZeroes,nextRowZeroes) => totalZeroes +
   nextRowZeroes, 0);
   const depthFirstSearch = (i, j, covered) => {
      if (arr[i][j] === 2){
         if (covered === totalZeroes + 1) count++;
         return;
      };
      for (let k = 0; k < 4; k++)
      if (i+dy[k] >= 0 && i+dy[k] < m && j+dx[k] >= 0 && j+dx[k] < n
      && arr[i+dy[k]][j+dx[k]] !== −1 ){
         arr[i][j] = −1;
         depthFirstSearch(i+dy[k],j+dx[k],covered+1);
         arr[i][j] = 0;
      }
      return;
   };
   for (let row = 0; row < m; row++)
   for (let col = 0; col < n; col++)
   if (arr[row][col] === 1){
      arr[row][col] = −1;
      depthFirstSearch(row,col,0);
      break;
   }
   return count;
};
console.log(uniquePaths(arr));

คำอธิบาย

• เราตั้งค่าตัวแปรเพื่ออำนวยความสะดวกในการวนซ้ำสี่ทิศทางเมื่อสำรวจกริด นับศูนย์ในเมทริกซ์เพื่อตรวจสอบความครอบคลุมเมื่อถึงเงื่อนไขพื้นฐานของการเรียกซ้ำ

• จากนั้นเราตั้งค่าฟังก์ชันแบ็คแทร็ก DFS (Depth First Search) เพื่อทำเครื่องหมายกริดด้วย -1 บนพาธที่ใช้งานอยู่ และเพื่อตรวจสอบความยาวของพาธเมื่อถึงเซลล์สุดท้าย

• และสุดท้าย เราเปิด DFS จากเซลล์เริ่มต้นเพื่อนับเส้นทางทั้งหมดและคืนค่าการนับ

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

2