मान लीजिए, हमें आयाम h x w का एक ग्रिड दिया गया है। ग्रिड में दो प्रकार की कोशिकाएँ होती हैं, श्वेत और काली कोशिकाएँ। श्वेत कोशिकाओं को '।' द्वारा दर्शाया जाता है, जबकि काली कोशिकाओं को '#' द्वारा दर्शाया जाता है। अब ग्रिड में कई काली कोशिकाएँ हैं जो बहुभुज बनाती हैं। हमें बहुभुज की भुजाओं की संख्या ज्ञात करनी है। यह ध्यान दिया जाना चाहिए कि ग्रिड की सबसे बाहरी कोशिकाएं हमेशा सफेद होती हैं।
इसलिए, यदि इनपुट h =4, w =4, ग्रिड ={"...", ".##.", ".##.", "...."} जैसा है, तो आउटपुट 4 होगा।
काली कोशिकाएँ एक वर्ग बनाती हैं, और एक वर्ग में 4 भुजाएँ होती हैं।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
sides := 0 for initialize i := 1, when i < h, update (increase i by 1), do: for initialize j := 1, when j < w, update (increase j by 1), do: bl := 0 if grid[i - 1, j - 1] is same as '#', then: (increase bl by 1) if grid[i - 1, j] is same as '#', then: (increase bl by 1) if grid[i, j - 1] is same as '#', then: (increase bl by 1) if grid[i, j] is same as '#', then: (increase bl by 1) if bl is same as 1 or 3, then: (increase sides by 1) 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