मान लीजिए कि हमारे पास एक 2-आयामी ग्रिड है, 4 प्रकार के वर्ग हैं -
-
एक वर्ग में 1 प्रारंभिक बिंदु के लिए है। ठीक एक शुरुआती वर्ग होगा।
-
एक वर्ग में 2 अंतिम बिंदु के लिए है। ठीक एक अंत वर्ग होगा।
-
एक वर्ग में 0 खाली वर्गों के लिए है और हम चल सकते हैं।
-
एक वर्ग -1 में यदि उन बाधाओं के लिए जिन्हें हम पार नहीं कर सकते।
हमें शुरुआती वर्ग से अंतिम वर्ग तक 4-दिशात्मक चलने की संख्या का पता लगाना है, जो हर गैर-बाधा वर्ग पर ठीक एक बार चलता है।
तो, अगर इनपुट इस तरह है -
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 2 | -1 |
तो आउटपुट 2 होगा, क्योंकि हमारे पास ये दो रास्ते हैं:(0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1),(1,0), (2,0), (2,1), (2,2) और (0,0), (1,0), (2,0), (2 ,1), (1,1), (0,1), (0,2), (0,3), (1,3), (1,2), (2,2)।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन dfs() को परिभाषित करें, यह एक 2D सरणी ग्रिड लेगा, i, j, ex, ey, खाली,
-
अगर i,j ग्रिड या ग्रिड की सीमा में नहीं है [i, j] -1 के समान है, तो -
-
वापसी 0
-
-
अगर ग्रिड [i, j] 2 के समान है, तो
-
खाली होने पर सही लौटें -1
-
-
एक्स:=0
-
(खाली 1 से घटाएं)
-
ग्रिड [i, j] :=-1
-
इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -
-
एनएक्स:=आई + डीआईआर [के, 0]
-
ny :=j + dir[k, 1]
-
x :=x + dfs (ग्रिड, nx, ny, ex, ey, खाली)
-
-
(खाली में 1 से बढ़ाएं)
-
ग्रिड [i, j] :=0
-
वापसी x
-
विधि से निम्न कार्य करें -
-
खाली :=0
-
n :=पंक्ति गणना, m :=स्तम्भों की संख्या
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
इनिशियलाइज़ j :=0 के लिए, जब j
-
अगर ग्रिड [i, j] 0 के समान है, तो
-
(खाली में 1 से बढ़ाएं)
-
-
अन्यथा जब ग्रिड [i, j] 1 के समान हो, तो -
-
एसएक्स:=मैं, एसवाई:=जे
-
-
अन्यथा जब ग्रिड [i, j] 2 के समान हो, तो -
-
उदा :=i, ey :=j
-
-
-
-
वापसी dfs (ग्रिड, sx, sy, ex, ey, खाली)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
public:
int dfs(vector<vector<int> >& grid, int i, int j, int ex, int ey,
int empty){
if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0
|| grid[i][j] == -1)
return 0;
if (grid[i][j] == 2) {
return empty == -1;
}
int x = 0;
empty--;
grid[i][j] = -1;
for (int k = 0; k < 4; k++) {
int nx = i + dir[k][0];
int ny = j + dir[k][1];
x += dfs(grid, nx, ny, ex, ey, empty);
}
empty++;
grid[i][j] = 0;
return x;
}
int uniquePathsIII(vector<vector<int> >& grid){
int empty = 0;
int sx, sy, ex, ey;
int n = grid.size();
int m = grid[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0)
empty++;
else if (grid[i][j] == 1) {
sx = i;
sy = j;
}
else if (grid[i][j] == 2) {
ex = i;
ey = j;
}
}
}
return dfs(grid, sx, sy, ex, ey, empty);
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
cout << (ob.uniquePathsIII(v));
} इनपुट
{{1,0,0,0},{0,0,0,0},{0,0,2,-1}} आउटपुट
2