ปัญหาอัลกอริทึม: รูปแบบ Backtracking ใน JavaScript

ภาพรวม

พิจารณาปัญหา Backtracking บนกริด 2 มิติ มี 4 ประเภทของช่อง:

• 1: จุดเริ่มต้น (มีเพียง 1 จุด)
• 2: จุดสิ้นสุด (มีเพียง 1 จุด)
• 0: ช่องว่างที่เดินผ่านได้
• -1: อุปสรรคที่เดินไม่ผ่าน

เราต้องเขียนฟังก์ชันคืนจำนวนเส้นทาง 4 ทิศทางจากจุดเริ่มต้นถึงจุดสิ้นสุด ที่เดินผ่านทุกช่องที่ไม่ใช่อุปสรรคครบ 1 ครั้ง

ตัวอย่างโค้ด

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((total, next) => total + next, 0);
  
  const depthFirstSearch = (i, j, covered) => {
    if (arr[i][j] === 2) {
      if (covered === totalZeroes + 1) count++;
      return;
    }
    for (let k = 0; k < 4; k++) {
      const ni = i + dy[k], nj = j + dx[k];
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && arr[ni][nj] !== -1) {
        arr[i][j] = -1;
        depthFirstSearch(ni, nj, covered + 1);
        arr[i][j] = 0;
      }
    }
  };
  
  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));

คำอธิบาย

• ตั้งค่าตัวแปรสำหรับการวน 4 ทิศทาง นับจำนวน 0 ในกริดเพื่อเช็คการครอบคลุมเมื่อถึงเงื่อนไขฐานของการเรียกซ้ำ
• ตั้งค่า DFS backtrack function ทำเครื่องหมายกริดเป็น -1 บนเส้นทางที่ใช้งาน และตรวจสอบความยาวเส้นทางเมื่อถึงช่องสิ้นสุด
• เริ่ม DFS จากช่องเริ่มต้น นับเส้นทางเต็มทั้งหมดและคืนจำนวน

ผลลัพธ์ในคอนโซล

2