एल्गोरिथम समस्या - जावास्क्रिप्ट में बैकट्रेसिंग पैटर्न

निम्नलिखित बैकट्रेसिंग समस्या पर विचार करें: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));

स्पष्टीकरण

• हम ग्रिड को पार करते समय चार दिशात्मक पुनरावृत्ति की सुविधा के लिए चर सेट करते हैं, पुनरावर्तन की आधार स्थिति तक पहुंचने पर कवरेज की जांच करने की अनुमति देने के लिए मैट्रिक्स में शून्य की गणना करें

• फिर हम सक्रिय पथ पर ग्रिड को -1 के साथ चिह्नित करने के लिए और फिनिश सेल तक पहुंचने पर पथ की लंबाई की जांच करने के लिए डीएफएस (गहराई पहली खोज) बैकट्रैक फ़ंक्शन सेट करते हैं

• और अंत में, हम सभी पूर्ण पथों को गिनने और गिनती वापस करने के लिए प्रारंभ सेल से DFS लॉन्च करते हैं

आउटपुट

और कंसोल में आउटपुट होगा -

2