মান লিজিয়ে, h × w মাত্রার একটি গ্রিড দেওয়া আছে যাতে দুটি ধরনের কক্ষ রয়েছে: ব্লক করা এবং আনব্লক করা। ব্লক করা কক্ষ মানে অ্যাক্সেস করা যাবে না এবং আনব্লক করা মানে অ্যাক্সেস করা যাবে। গ্রিডটি ২D অ্যারে আকারে দেওয়া আছে যেখানে ব্লক করা কক্ষ '#' এবং আনব্লক করা কক্ষ '.' দিয়ে দেখানো হয়েছে। এখন আমাদের একটি আনব্লক কক্ষ থেকে অন্য একটি আনব্লক কক্ষে যেতে হবে। আমরা শুধু দুটি মোভ করতে পারি: খাড়া বা দাঁড়ি। ডায়াগোনালি যেতে পারব না। লক্ষ্য করুন যে, আমরা শুধু আনব্লক কক্ষেই যেতে পারি। আমাদের লক্ষ্য হলো গ্রিডে একটি আনব্লক কক্ষ থেকে অন্য আনব্লক কক্ষে যেতে সর্বোচ্চ কতগুলো মোভ লাগে তা বের করা।
যেমন, ইনপুট হলে h = 4, w = 4, grid = {"..#.", "#.#.", "..##", "###."}, তবে আউটপুট হবে 4।
(0,0) কক্ষ থেকে সর্বোচ্চ ৪টি মোভ লাগে (2, 0) কক্ষে পৌঁছাতে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
xdir অ্যারে সংজ্ঞায়িত করুন আকার: 4 := {1, 0, -1, 0} ydir অ্যারে সংজ্ঞায়িত করুন আকার: 4 := {0, 1, 0, -1} dist ২D অ্যারে সংজ্ঞায়িত করুন reset ২D অ্যারে সংজ্ঞায়িত করুন res := 0 i := 0 থেকে h-1 পর্যন্ত: j := 0 থেকে w-1 পর্যন্ত: dist := reset if grid[i, j] == '.', তবে: dist[i, j] := 0 q কিউ সংজ্ঞায়িত করুন ইন্টিজার পেয়ার ধারণকারী q-তে make_pair(i, j) যোগ করুন while (q খালি নয়): x := q-র বামপাশের উপাদানের ১ম মান y := q-র বামপাশের উপাদানের ২য় মান res := max(dist[x, y], res) q-র বামপাশের উপাদান মুছুন k := 0 থেকে ৩ পর্যন্ত: px := x + xdir[k] py := y + ydir[k] if px >= 0 এবং px < h এবং py >= 0 এবং py < w, তবে: if grid[px, py] == '.', তবে: if dist[px, py] == -1, তবে: dist[px, py] := dist[x, y] + 1 q-তে pair(px, py) যোগ করুন return res উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int solve(int h, int w, vector<string> grid){ int xdir[4] = {1, 0, -1, 0}; int ydir[4] = {0, 1, 0, -1}; vector<vector<int>> dist(h, vector<int>(w, -1)); vector<vector<int>> reset(h, vector<int>(w, -1)); int res = 0; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ dist = reset; if(grid[i][j] == '.'){ dist[i][j] = 0; queue<pair<int,int>> q; q.push(make_pair(i, j)); while(!q.empty()){ int x = q.front().first; int y = q.front().second; res = max(dist[x][y], res); q.pop(); for(int k = 0; k < 4; k++){ int px = x + xdir[k]; int py = y + ydir[k]; if(px >= 0 && px < h && py >= 0 && py < w){ if(grid[px][py] == '.'){ if(dist[px][py] == -1){ dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py)); } } } } } } } } return res; } int main() { int h = 4, w = 4; vector<string> grid = {"..#.", "#.#.", "..##", "###."}; cout << solve(h, w, grid); return 0; } ইনপুট
4, 4, {"..#.", "#.#.", "..##", "###."} আউটপুট
4
