জাভাস্ক্রিপ্টে ব্যাকট্রেসিং প্যাটার্ন: গ্রিডে পাথ কাউন্ট করা

নিচের ব্যাকট্রেসিং সমস্যা বিবেচনা করুন: একটি ২-ডাইমেনশনাল গ্রিডে ৪ টাইপের স্কোয়ার আছে:

১ রিপ্রেজেন্ট করে স্টার্টিং স্কোয়ার। ঠিক একটি স্টার্টিং স্কোয়ার আছে।
২ রিপ্রেজেন্ট করে এন্ডিং স্কোয়ার। ঠিক একটি এন্ডিং স্কোয়ার আছে।
০ রিপ্রেজেন্ট করে খালি স্কোয়ার যেটি ওভার যাওয়া যায়।
−১ রিপ্রেজেন্ট করে বাধা যেটি ওভার যাওয়া যায় না।

আমাদের একটি ফাংশন লিখতে হবে যা স্টার্টিং স্কোয়ার থেকে এন্ডিং স্কোয়ার পর্যন্ত ৪-ডিরেকশনাল ওকের সংখ্যা রিটার্ন করবে, যেটি প্রতিটি নন-অবস্টাকল স্কোয়ার ঠিক একবার ওভার করে।

উদাহরণ

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 (ডেপথ ফার্স্ট সার্চ) ব্যাকট্র্যাক ফাংশন সেট আপ করা যাতে অ্যাক্টিভ পাথে -১ মার্ক করা হয় এবং ফিনিশ সেলে পৌঁছালে পাথ লেথ চেক করা হয়
এবং অবশেষে, স্টার্ট সেল থেকে DFS লঞ্চ করা যাতে সব ফুল পাথ কাউন্ট করা যায় এবং কাউন্ট রিটার্ন করা হয়

আউটপুট

কনসোলে আউটপুট হবে: