मान लीजिए हमारे पास एक 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() फ़ंक्शन परिभाषित करें जो ग्रिड, i, j, ex, ey, empty लेता है
यदि i,j सीमा से बाहर या grid[i][j] == -1 तो 0 लौटाएं
यदि grid[i][j] == 2 तो empty == -1 होने पर true लौटाएं
x := 0, empty घटाएं, grid[i][j] := -1
चार दिशाओं में पुनरावर्ती कॉल करें और परिणाम जोड़ें
empty बढ़ाएं, grid[i][j] := 0, x लौटाएं
मुख्य विधि से: खाली सेल्स गिनें, प्रारंभ और अंत ढूंढें, dfs कॉल करें
उदाहरण
#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);
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
cout << (ob.uniquePathsIII(v));
return 0;
}
इनपुट
{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}
आउटपुट
2
