ধরুন, h*w মাত্রার একটি গ্রিড আছে। সেল পজিশনে একটি রোবট রয়েছে (0, 0) এবং এটিকে অবস্থানে যেতে হবে (h - 1, w - 1)। একটি গ্রিডে দুই ধরনের সেল আছে, ব্লক করা এবং আনব্লক করা। রোবটটি অবরুদ্ধ কোষগুলির মধ্য দিয়ে যেতে পারে তবে অবরুদ্ধ কোষগুলির মধ্য দিয়ে যেতে পারে না। রোবট চার দিকে যেতে পারে; এটি বাম, ডান, উপরে এবং নীচে যেতে পারে। কিন্তু রোবট একটি সেল থেকে অন্য কোন দিকে যেতে পারে (আগের সেলটি উপেক্ষা করে), তাই আমাদের শুধুমাত্র একটি পথ তৈরি করতে হবে এবং সেই পথের মধ্যে নেই এমন অন্যান্য সমস্ত কোষকে ব্লক করতে হবে। আমাদের খুঁজে বের করতে হবে এবং (0, 0) থেকে (h - 1, w - 1) পর্যন্ত রোবটের জন্য একটি পথ তৈরি করতে আমাদের কতগুলি সেল ব্লক করতে হবে এবং যদি কোনও পথ সম্ভব না হয় তবে আমরা -1 ফেরত দিই।
সুতরাং, যদি ইনপুটটি h =4, w =4, গ্রিড ={..#.", "#.#", "#.##", "#..."} হয়, তাহলে আউটপুট 2 হবে।
(0, 0) থেকে (3, 3) পর্যন্ত একটি একক পথ তৈরি করতে আমাদের শুধুমাত্র দুটি ঘর ব্লক করতে হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define one 2D array dp
dp[0, 0] := 0
Define an array moves containing pairs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
Define one queue q
insert pair (0, 0) at the end of q
while (not q is empty), do:
p := first element of q
delete first element from q
for initialize i := 0, when i < 4, update (increase i by 1), do:
row := first value of p + first value of moves[i]
col := second value of p + second value of moves[i]
if row < 0 or row > h - 1 or col < 0 or col > w - 1, then:
Ignore following part, skip to the next iteration
if grid[row, col] is same as '#', then:
Ignore following part, skip to the next iteration
if dp[first value of p, second value of p] + 1 < dp[row, col], then:
dp[row, col] := dp[first value of p, second value of p] + 1
insert pair(row, col) into q
if dp[h - 1, w - 1] is same as 2500, then:
return -1
count := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
for initialize j := 0, when j < w, update (increase j by 1), do:
if grid[i, j] is same as '.', then:
(increase count by 1)
return count - (dp[h - 1, w - 1] + 1) উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int solve(int h, int w, vector<string> grid){
vector<vector<int>> dp(h, vector<int>(w, 2500));
dp[0][0] = 0;
vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
while (!q.empty()) {
auto p = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int row = p.first + moves[i].first;
int col = p.second + moves[i].second;
if (row < 0 || row > h - 1 || col < 0 || col > w - 1) continue;
if (grid[row][col] == '#')
continue;
if (dp[p.first][p.second] + 1 < dp[row][col]) {
dp[row][col] = dp[p.first][p.second] + 1; q.push(make_pair(row, col));
}
}
}
if (dp[h - 1][w - 1] == 2500) {
return -1;
}
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (grid[i][j] == '.') count++;
}
}
return count - (dp[h - 1][w - 1] + 1);
}
int main() {
int h = 4, w = 4;
vector<string> grid = {"..#.", "#.#.", "#.##", "#..."};
cout<< solve(h, w, grid);
return 0;
} ইনপুট
4, 4, {"..#.", "#.#.", "#.##", "#..."}
আউটপুট
2
