ধরুন আমাদের একটি 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, empty,
-
যদি i,j গ্রিড বা গ্রিডের পরিসরে না থাকে [i, j] -1 এর মতো, তাহলে −
-
রিটার্ন 0
-
-
যদি গ্রিড[i, j] 2 এর মত হয়, তাহলে
-
খালি হলে true রিটার্ন করুন -1
-
-
x :=0
-
(1 দ্বারা খালি কমান)
-
গ্রিড[i, j] :=-1
-
আরম্ভ করার জন্য k :=0, যখন k <4, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −
-
nx :=i + dir[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 এর মত হয়, তখন −
-
sx :=i, sy :=j
-
-
অন্যথায় যখন গ্রিড[i, j] 2 এর মত হয়, তাহলে −
-
ex :=i, ey :=j
-
-
-
-
রিটার্ন ডিএফএস (গ্রিড, এসএক্স, সি, এক্স, ই, খালি)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
