মান লিজিয়ে, h × w মাত্রার একটি গ্রিড আছে। (0, 0) কক্ষে একটি রোবট আছে এবং সেটিকে (h-1, w-1) কক্ষে যেতে হবে। গ্রিডে দুটি ধরনের কক্ষ রয়েছে: ব্লক করা এবং আনব্লক করা। রোবট আনব্লক করা কক্ষ দিয়ে যেতে পারে কিন্তু ব্লক করা কক্ষ দিয়ে যেতে পারে না। রোবট চার দিকে যেতে পারে: বাম, ডান, উপর, নিচ। কিন্তু রোবট যেকোনো দিক থেকে যেকোনো কক্ষে যেতে পারে (পূর্বের কক্ষকে উপেক্ষা করে), তাই আমাদের শুধু একটি পথ বানাতে হবে এবং পথের বাইরের সব কক্ষ ব্লক করতে হবে। আমাদের লক্ষ্য হলো (0, 0) থেকে (h-1, w-1) পর্যন্ত একক পথ বানাতে কতগুলো কক্ষ ব্লক করতে হবে তা বের করা এবং যদি পথ সম্ভব না হয়, তবে -1 রিটার্ন করা।
যেমন, ইনপুট হলে h = 4, w = 4, grid = {"..#.", "#.#.", "#.##", "#..."}, তবে আউটপুট হবে 2।
(0, 0) থেকে (3, 3) পর্যন্ত একক পথ বানাতে শুধু দুটি কক্ষ ব্লক করতে হবে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
dp ২D অ্যারে সংজ্ঞায়িত করুন dp[0, 0] := 0 moves অ্যারে সংজ্ঞায়িত করুন পেয়ারসহ = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} q কিউ সংজ্ঞায়িত করুন q-তে pair(0, 0) যোগ করুন while (q খালি নয়): p := q-র প্রথম উপাদান q-র প্রথম উপাদান মুছুন i := 0 থেকে ৩ পর্যন্ত: row := p.first + moves[i].first 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-তে pair(row, col) যোগ করুন if dp[h-1, w-1] == 2500, তবে: return -1 count := 0 i := 0 থেকে h-1 পর্যন্ত: j := 0 থেকে w-1 পর্যন্ত: if grid[i, j] == '.', তবে: count ১ বাড়িয়ে 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
