মান লিজিয়ে, h × w মাত্রার একটি গ্রিড দেওয়া আছে। গ্রিডের কক্ষগুলোতে বল্ব বা বাধা থাকতে পারে। একটি বল্বयुक्त কক্ষ নিজে এবং তার চারদিকের কক্ষগুলোকে আলোকিত করে এবং আলো বাধা কক্ষ না থাকা পর্যন্ত চলে। বাধা কক্ষ আলোকিত হয় না এবং বল্বের আলো বাধা হয়। বল্ব কক্ষের অবস্থান 'bulb' অ্যারেতে এবং বাধা কক্ষের অবস্থান 'obstacles' অ্যারেতে দেওয়া আছে। আমাদের লক্ষ্য হলো গ্রिडে মোট কতগুলো কক্ষ আলোকিত হয়েছে তা বের করা।
যেমন, ইনপুট হলে h = 4, w = 4, bulb = {{1, 1}, {2, 2}, {3, 3}}, obstacle = {{0, 0}, {2, 3}}, তবে আউটপুট হবে 13।
চিত্র থেকে আমরা গ্রিডে আলোকিত কক্ষগুলো দেখতে পাচ্ছি।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
bulbSize := bulb-র আকার blockSize := obstacle-র আকার grid ২D অ্যারে সংজ্ঞায়িত করুন i := 0 থেকে bulbSize-1 পর্যন্ত: x := bulb[i]-র ১ম মান y := bulb[i]-র ২য় মান grid[x, y] := 1 i := 0 থেকে blockSize-1 পর্যন্ত: x := obstacle[i]-র ১ম মান y := obstacle[i]-র ২য় মান grid[x, y] := 2 result := h * w check ২D অ্যারে সংজ্ঞায়িত করুন i := 0 থেকে h-1 পর্যন্ত: gd := 0 j := 0 থেকে w-1 পর্যন্ত: if grid[i, j] == 2, তবে: gd := 0 if grid[i, j] == 1, তবে: gd := 1 check[i, j] := check[i, j] OR gd gd := 0 j := w-1 থেকে ০ পর্যন্ত: if grid[i, j] == 2, তবে: gd := 0 if grid[i, j] == 1, তবে: gd := 1 check[i, j] := check[i, j] OR gd j := 0 থেকে w-1 পর্যন্ত: k := 0 i := 0 থেকে h-1 পর্যন্ত: if grid[i, j] == 2, তবে: k := 0 if grid[i, j] == 1, তবে: k := 1 check[i, j] := check[i, j] OR k k := 0 i := h-1 থেকে ০ পর্যন্ত: if grid[i, j] == 2, তবে: k := 0 if grid[i, j] == 1, তবে: k := 1 check[i, j] := check[i, j] OR k i := 0 থেকে h-1 পর্যন্ত: j := 0 থেকে w-1 পর্যন্ত: result := result - NOT(check[i, j]) return result
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int solve(int h, int w, vector<pair<int, int>> bulb, vector<pair<int, int>> obstacle){ int bulbSize = bulb.size(); int blockSize = obstacle.size(); vector<vector<int>> grid(h, vector<int>(w, 0)); for (int i = 0; i < bulbSize; i++) { int x = bulb[i].first; int y = bulb[i].second; grid[x][y] = 1; } for (int i = 0; i < blockSize; i++) { int x = obstacle[i].first; int y = obstacle[i].second; grid[x][y] = 2; } int result = h * w; vector<vector<bool>> check(h, vector<bool>(w, 0)); for (int i = 0; i < h; i++) { bool gd = 0; for (int j = 0; j < w; j++) { if (grid[i][j] == 2) gd = 0; if (grid[i][j] == 1) gd = 1; check[i][j] = check[i][j] | gd; } gd = 0; for (int j = w - 1; j >= 0; j--) { if (grid[i][j] == 2) gd = 0; if (grid[i][j] == 1) gd = 1; check[i][j] = check[i][j] | gd; } } for (int j = 0; j < w; j++) { bool k = 0; for (int i = 0; i < h; i++) { if (grid[i][j] == 2) k = 0; if (grid[i][j] == 1) k = 1; check[i][j] = check[i][j] | k; } k = 0; for (int i = h - 1; i >= 0; i--) { if (grid[i][j] == 2) k = 0; if (grid[i][j] == 1) k = 1; check[i][j] = check[i][j] | k; } } for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) result -= !check[i][j]; return result; } int main() { int h = 4, w = 4; vector<pair<int, int>> bulb = {{1, 1}, {2, 2}, {3, 3}}, obstacle = {{0, 0}, {2, 3}}; cout<< solve(h, w, bulb, obstacle); return 0; } ইনপুট
4, 4, {{1, 1}, {2, 2}, {3, 3}}, {{0, 0}, {2, 3}} আউটপুট
13
