मान लीजिए एक ग्रिड दिया गया है जिसमें दो प्रकार की सेल्स हैं: काली ('#') और सफेद ('.')। ग्रिड को स्ट्रिंग्स की सरणी के रूप में दिया गया है। हमें निम्न कार्य करना है:
- प्रत्येक सफेद सेल को काला करें जो किसी काली सेल के साथ भुजा साझा करती है। यह ऑपरेशन तब तक दोहराएँ जब तक ग्रिड की हर सेल काली न हो जाए।
- ग्रिड की सभी सेल्स को काला करने में लगी पुनरावृत्तियों की संख्या गिनें। ग्रिड में प्रारंभ में कम से कम एक काली सेल होनी चाहिए।
उदाहरण के लिए, यदि इनपुट है h = 4, w = 4, grid = {"#...", ".#..", "....", "...#"}, तो आउटपुट 3 होगा।
सभी सेल्स को काला करने में 3 पुनरावृत्तियाँ लगती हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
आकार 4 के सरणी dx := {1, 0, -1, 0} परिभाषित करें
आकार 4 के सरणी dy := {0, 1, 0, -1} परिभाषित करें
एक 2D सरणी distance परिभाषित करें
एक कतार q परिभाषित करें जिसमें पूर्णांक युग्म हों
i := 0 से h-1 तक:
j := 0 से w-1 तक:
यदि grid[i][j] == '#', तो:
distance[i][j] := 0
q में युग्म (i, j) डालें
जब तक q खाली न हो:
now := q का पहला तत्व
q से हटाएँ
dir := 0 से 3 तक:
cx := now.first + dx[dir]
cy := now.second + dy[dir]
यदि cx < 0 या cx >= h या cy < 0 या cy >= w, तो जारी रखें
यदि distance[cx][cy] == -1, तो:
distance[cx][cy] := distance[now.first][now.second] + 1
q में युग्म (cx, cy) डालें
ans := 0
i := 0 से h-1 तक:
j := 0 से w-1 तक:
ans := max(ans, distance[i][j])
ans प्रिंट करें
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void solve(int h, int w, vector <string> grid){ int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, 1, 0, -1 }; vector<vector<int>> distance(h, vector<int>(w, -1)); queue<pair<int, int>> q; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (grid[i][j] == '#') { distance[i][j] = 0; q.push(pair<int, int>(i,j)); } } } while (!q.empty()) { auto now = q.front(); q.pop(); for (int dir = 0; dir < 4; dir++) { int cx = now.first + dx[dir]; int cy = now.second + dy[dir]; if (cx < 0 || cx >= h || cy < 0 || cy >= w) continue; if (distance[cx][cy] == -1) { distance[cx][cy] = distance[now.first][now.second] + 1; q.push(pair<int, int> (cx, cy)); } } } int ans = 0; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ans = max(ans, distance[i][j]); } } cout << ans << endl; } int main() { int h = 4, w = 4; vector<string> grid = {"#...", ".#.." , "....", "...#"}; solve(h, w, grid); return 0; }
इनपुट
4, 4, {"#...", ".#.." , "....", "...#"}
आउटपुट
3
