সি++-এ ইউনিক পাথ III

মান লিইয়ে নিই একটি 2-ডাইমেনশনাল গ্রিড রয়েছে, যেখানে ৪ ধরনের স্কোয়ার রয়েছে:

• একটি স্কোয়ারে 1 হলো শুরুর পয়েন্ট। ঠিক একটি শুরুর স্কোয়ার থাকবে।

• একটি স্কোয়ারে 2 হলো শেষ পয়েন্ট। ঠিক একটি শেষ স্কোয়ার থাকবে।

• একটি স্কোয়ারে 0 হলো খালি স্কোয়ার যেখানে আমরা চলাফেরা করতে পারি।

• একটি স্কোয়ারে -1 হলো বাধা যেখানে আমরা চলাফেরা করতে পারি না।

আমাদের শুরুর স্কোয়ার থেকে শেষ স্কোয়ার পর্যন্ত 4-দিকের পথের সংখ্যা বের করতে হবে, যেটি প্রতিটি নন-অবস্ট্রাকল স্কোয়ারকে ঠিক একবার দিয়ে যায়।

সুতরাং, যদি ইনপুট হয়:

তব আউটপুট হবে ২, কারণ আমাদের এই দুটি পথ রয়েছে: (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 অ্যারে grid, i, j, ex, ey, empty গ্রহণ করবে,
• যদি i,j গ্রিডের রেঞ্জে না থাকে বা grid[i, j] -1-এর সমান হয়, তবে:
  • 0 ফেরত দিন
• যদি grid[i, j] 2-এর সমান হয়, তবে:
  • empty -1 হলে true ফেরত দিন
• x := 0
• (empty 1 কমান)
• grid[i, j] := -1
• k := 0 থেকে आरंभ করুন, जब k < 4, আপডেট করুন (k 1 বাড়ান), করুন:
  • nx := i + dir[k, 0]
  • ny := j + dir[k, 1]
  • x := x + dfs(grid, nx, ny, ex, ey, empty)
• (empty 1 বাড়ান)
• grid[i, j] := 0
• x ফেরত দিন
• মূল পদ্ধতিতে নিম্নলিখিত কাজ করুন:
  • empty := 0
  • n := সারি সংখ্যা, m := কলাম সংখ্যা
  • i := 0 থেকে आरंभ করুন, जब i < n, আপডেট করুন (i 1 বাড়ান), করুন:
    • j := 0 থেকে आरंभ করুন, जब j < m, আপডেট করুন (j 1 বাড়ান), করুন:
      • যদি grid[i, j] 0-এর সমান হয়, তবে (empty 1 বাড়ান)
      • অন্যথায় যদি grid[i, j] 1-এর সমান হয়, তবে sx := i, sy := j
      • অন্যথায় যদি grid[i, j] 2-এর সমান হয়, তবে ex := i, ey := j
  • dfs(grid, sx, sy, ex, ey, empty) ফেরত দিন

উদাহরণ

বेहतर समझ के लिए निम्नलिखিত कार्यान्वयन देखें:

#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