অ্যালগরিদম সমস্যা - জাভাস্ক্রিপ্টে ব্যাকট্রেসিং প্যাটার্ন

নিম্নলিখিত ব্যাকট্রেসিং সমস্যাটি বিবেচনা করুন:একটি 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 (ডেপথ ফার্স্ট সার্চ) ব্যাকট্র্যাক ফাংশন সেট আপ করি সক্রিয় পাথে −1 দিয়ে গ্রিড চিহ্নিত করতে এবং ফিনিশ সেল পৌঁছে গেলে পাথের দৈর্ঘ্য পরীক্ষা করতে
এবং সবশেষে, আমরা সমস্ত সম্পূর্ণ পথ গণনা করতে এবং গণনা ফেরত দিতে স্টার্ট সেল থেকে DFS চালু করি

আউটপুট

এবং কনসোলে আউটপুট হবে −