মান লিখুন: H সারি এবং W কলাম বিশিষ্ট একটি ম্যাট্রিক্স দেওয়া আছে। সেলগুলো '.', '#' ধারণ করে। '.' বোঝায় পাসেবল স্পেস, '#' বোঝায় ব্লক। আমল তার বাড়ি থেকে বাজার যাবে। বাড়ি টপ-লেফ্ট কর্নারে, বাজার বটম-রাইট কর্নারে। আমল উপর, নিচ, বাম, ডানে এক সেল যেতে পারে পাসেবল সেলে। সে ব্লক সেলে যেতে পারবে না। কিন্তু তার শারীরিক শক্তি দিয়ে সে ২x২ আকারের একটি বর্গাকার অঞ্চলের সকল ব্লক এক পাঞ্চে ধ্বংস করতে পারে, সেগুলো পাসেবল করে দিতে পারে। বাজার পর্যন্ত পৌঁছানোর জন্য ন্যূনতম কত পাঞ্চ দরকার তা বের করতে হবে।
উদাহরণ
ইনপুট ম্যাট্রিক্স (চিত্রে দেখানো হয়েছে)। আউটপুট: 1, কারণ চিত্রে চিহ্নিত ২x২ ব্লক ধ্বংস করলে পথ পাওয়া যায়।
সমাধানের ধাপসমূহ
n := ম্যাট্রিক্সের সারি, m := কলাম
dist ২ডি অ্যারে (n+1)x(m+1) ইনফিনিট দিয়ে ইনিশিয়ালাইজ
dq ডিক
(0,0) dq-তে পুশ করুন, dist[0][0] := 0
যখন dq খালি নয়:
v := dq.front(), dq.pop_front()
for i := 0 থেকে 3:
x := dx[i] + v[0], y := dy[i] + v[1]
যদি x,y ভ্যালিড:
যদি matrix[x][y] == '.':
যদি dist[x][y] > dist[v[0]][v[1]]:
dist[x][y] := dist[v[0]][v[1]]
dq.push_front({x,y})
অন্যথায়:
for p := x-1 থেকে x+1:
for q := y-1 থেকে y+1:
যদি p,q ভ্যালিড:
যদি dist[p][q] > dist[v[0]][v[1]] + 1:
dist[p][q] := dist[v[0]][v[1]] + 1
dq.push_back({p,q})
dist[n-1][m-1] রিটার্ন করুন
C++ বাস্তবায়ন
#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
