মান লিজিয়ে, h × w মাত্রার একটি গ্রিড দেওয়া আছে। গ্রিডে দুটি ধরনের কক্ষ রয়েছে: সাদা এবং কালো। সাদা কক্ষ '.' দিয়ে এবং কালো কক্ষ '#' দিয়ে প্রতীকীভাবে দেখানো হয়েছে। গ্রিডে একাধিক কালো কক্ষ রয়েছে যা একটি পলিগন গঠন করে। আমাদের লক্ষ্য হলো সেই পলিগনের বাহুর সংখ্যা বের করা। একটি বিষয় লক্ষ্য করুন, গ্রিডের বাহিরের কক্ষগুলো সবসময় সাদা থাকে।
যেমন, ইনপুট হলে h = 4, w = 4, grid = {"....", ".##.", ".##.", "...."}, তবে আউটপুট হবে 4।
কালো কক্ষগুলো একটি বর্গাকার গঠন করেছে, এবং একটি বর্গের ৪টি বাহু থাকে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
sides := 0 i := 1 থেকে h-1 পর্যন্ত: j := 1 থেকে w-1 পর্যন্ত: bl := 0 if grid[i-1, j-1] == '#', তবে: bl ১ বাড়িয়ে if grid[i-1, j] == '#', তবে: bl ১ বাড়িয়ে if grid[i, j-1] == '#', তবে: bl ১ বাড়িয়ে if grid[i, j] == '#', তবে: bl ১ বাড়িয়ে if bl == 1 বা bl == 3, তবে: sides ১ বাড়িয়ে return sides
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; void solve(int h, int w, vector<string> grid){ int sides = 0; for(int i = 1; i < h; i++) { for(int j = 1; j < w; j++) { int bl = 0; if(grid.at(i - 1).at(j - 1) == '#') { bl++; } if(grid.at(i - 1).at(j) == '#') { bl++; } if(grid.at(i).at(j - 1) == '#') { bl++; } if(grid.at(i).at(j) == '#') { bl++; } if(bl == 1 or bl == 3) { sides++; } } } cout << sides; } int main() { int h = 4, w = 4; vector<string> grid = {"....", ".##.", ".##.", "...."}; solve(h, w, grid); return 0; } ইনপুট
4, 4, {"....", ".##.", ".##.", "...."} আউটপুট
4
