निम्नलिखित बैकट्रेसिंग समस्या पर विचार करें: एक 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 लॉन्च करते हैं और काउंट लौटाते हैं
आउटपुट
कंसोल में आउटपुट होगा -
2
