মান লিজিয়ে, h × w মাত্রার একটি গ্রিড দেওয়া আছে। গ্রিডের কক্ষগুলোতে বল্ব বা বাধা থাকতে পারে। একটি বল্বयुक्त কক্ষ তার ডান, বাম, উপর ও নিচের কক্ষগুলোকে আলোকিত করে এবং আলো বাধা কক্ষ না থাকা পর্যন্ত চলে। বাধা কক্ষ আলোকিত হয় না এবং বল্বের আলো অন্য কক্ষে পৌঁছানোর বাধা হয়। গ্রিডটি স্ট্রিং অ্যারে আকারে দেওয়া আছে, যেখানে '#' বাধা এবং '.' শূন্য কক্ষ বোঝায়। আমাদের শুধু একটি বল্ব আছে এবং আমাদের লক্ষ্য হলো গ্রিডে সর্বোচ্চ কতগুলো কক্ষ আলোকিত করা যায় তা বের করা বল্বটি বুদ্ধিমানীपूर्णভাবে রাখায়।
যেমন, ইনপুট হলে h = 4, w = 4, grid = {"#...", "....", "...#", "...."}, তবে আউটপুট হবে 7।
চিত্র থেকে আমরা গ্রিডে আলোকিত কক্ষগুলো দেখতে পাচ্ছি।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
first ২D অ্যারে সংজ্ঞায়িত করুন i := 0 থেকে h-1 পর্যন্ত: count := 0 j := 0 থেকে w-1 পর্যন্ত: if grid[i, j] == '#', তবে: count := 0 continue অন্যথায়: first[i, j] := count count ১ বাড়িয়ে k := 0 j := w-1 থেকে ০ পর্যন্ত: if grid[i, j] == '#', তবে: k := 0 continue অন্যথায়: k := max(k, first[i, j]) first[i, j] := k second ২D অ্যারে সংজ্ঞায়িত করুন j := 0 থেকে w-1 পর্যন্ত: count := 0 i := 0 থেকে h-1 পর্যন্ত: if grid[i, j] == '#', তবে: count := 0 continue অন্যথায়: second[i, j] := count count ১ বাড়িয়ে k := 0 i := h-1 থেকে ০ পর্যন্ত: if grid[i, j] == '#', তবে: k := 0 continue অন্যথায়: k := max(k, second[i, j]) second[i, j] := k result := 0 i := 0 থেকে h-1 পর্যন্ত: j := 0 থেকে w-1 পর্যন্ত: result := max(result, first[i, j] + second[i, j]) return result + 1
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int solve(int h, int w, vector<string> grid){ vector<vector<int>> first(h, vector<int> (w)); for(int i = 0; i < h; i++) { int count = 0; for(int j = 0; j < w; j++) { if(grid[i][j] == '#') { count = 0; continue; } else { first[i][j] = count; count++; } } int k = 0; for(int j = w-1; j >= 0; j--) { if(grid[i][j] == '#') { k = 0; continue; } else { k = max(k, first[i][j]); first[i][j] = k; } } } vector<vector<int>> second(h, vector<int> (w)); for(int j = 0; j < w; j++) { int count = 0; for(int i = 0; i < h; i++) { if(grid[i][j] == '#') { count = 0; continue; } else { second[i][j] = count; count++; } } int k = 0; for(int i = h-1; i >= 0; i--) { if(grid[i][j] == '#') { k = 0; continue; } else { k = max(k, second[i][j]); second[i][j] = k; } } } int result = 0; for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { result = max(result, first[i][j] + second[i][j]); } } return result + 1; } int main() { int h = 4, w = 4; vector<string> grid = {"#...", "....", "...#", "...."}; cout<< solve(h, w, grid); return 0; } ইনপুট
4, 4, {"#...", "....", "...#", "...."} আউটপুট
7
