ধরুন আমাদের একটি ম্যাট্রিক্স আছে যেখানে H সারি এবং W কলাম রয়েছে। কোষ হয় '.' ধারণ করে। অথবা '#'। বিন্দু '।' পাসযোগ্য স্থান নির্দেশ করে, এবং '#' ব্লক নির্দেশ করে। অমল তার বাড়ি থেকে বাজারে যাবে। তার বাড়ি উপরের-বাম কোণে ঘরে, এবং বাজারটি নীচে-ডানদিকে। আমাল একটি কোষকে উপরে, নীচে, বাম বা ডানে একটি পাসযোগ্য কোষে সরাতে পারে। সে শহর ছেড়ে যেতে পারে না। তিনি একটি অবরুদ্ধ কক্ষে প্রবেশ করতে পারবেন না। যাইহোক, তার শারীরিক শক্তি তাকে একটি ঘুষি দিয়ে তার পছন্দের 2×2 কোষ সহ একটি বর্গাকার অঞ্চলের সমস্ত ব্লক ধ্বংস করতে দেয়, এই কোষগুলিকে প্রবেশযোগ্য করে তোলে। বাজারে পৌঁছানোর জন্য অমলের জন্য ন্যূনতম কতগুলি ঘুষি দরকার তা আমাদের খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট মত হয়
| । | । | # | । | । |
| # | । | # | । | # |
| # | # | । | # | # |
| # | । | # | । | # |
| । | । | # | । | । |
তাহলে আউটপুট হবে 1, কারণ আমরা গ্রিডটিকে −
এর মত করতে পারি| । | । | # | । | । |
| # | । | । | । | # |
| # | # | । | । | # |
| # | । | # | । | # |
| । | । | # | । | । |
চিহ্নিত বাক্সগুলি ধ্বংস করে
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
n := row count of matrix
m := column count of matrix
Define one 2D array dist of order (n + 1) x (m + 1)
Define one deque dq
insert ( 0, 0 ) at the beginning of dq
dist[0, 0] := 0
while (not dq is empty), do:
v := first element of dq
delete front element from dq
for initialize i := 0, when i < 4, update (increase i by 1), do:
x := dx[i] + v[0]
y := dy[i] + v[1]
if x >= 0 and x < n and y >= 0 and y < m, then:
if matrix[x, y] is same as '.', then:
if dist[x, y] > dist[v[0], v[1]], then:
dist[x, y] := dist[v[0], v[1]]
insert pair { x, y } at the beginning of dq
Otherwise
for initialize p := x - 1, when p <= x + 1, update (increase p by 1), do:
for initialize q := y - 1, when q <= y + 1, update (increase q by 1), do:
if p >= 0 and p < n and q >= 0 and q < m, then:
if dist[p, q] > dist[v[0], v[1]] + 1, then:
dist[p, q] := dist[v[0], v[1]] + 1
insert pair { p, q } at the end of dq
return dist[n - 1, m - 1] এর শেষে 1 সন্নিবেশ জোড়া উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int solve(vector<vector<char>> matrix){
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
deque<array<int, 2>> dq;
dq.push_front({ 0, 0 });
dist[0][0] = 0;
while (!dq.empty()){
auto v = dq.front();
dq.pop_front();
for (int i = 0; i < 4; i++){
int x = dx[i] + v[0], y = dy[i] + v[1];
if (x >= 0 && x < n && y >= 0 && y < m){
if (matrix[x][y] == '.'){
if (dist[x][y] > dist[v[0]][v[1]]){
dist[x][y] = dist[v[0]][v[1]];
dq.push_front({ x, y });
}
} else{
for (int p = x - 1; p <= x + 1; p++){
for (int q = y - 1; q <= y + 1; q++){
if (p >= 0 && p < n && q >= 0 && q < m){
if (dist[p][q] > dist[v[0]][v[1]] + 1){
dist[p][q] = dist[v[0]][v[1]] + 1;
dq.push_back({ p, q });
}
}
}
}
}
}
}
}
return dist[n - 1][m - 1];
}
int main(){
vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } };
cout << solve(matrix) << endl;
} ইনপুট
{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, {
'.', '.', '#', '.', '.' } } আউটপুট
1
