समस्या विवरण
हमें बाइनरी मानों (0 और 1) का एक ग्रिड दिया गया है जहां 1 ईंटों (bricks) को दर्शाते हैं। एक ईंट नहीं गिरेगी यदि:
- वह सीधे ग्रिड के शीर्ष से जुड़ी है, या
- उसके कम से कम एक आसन्न (ऊपर, नीचे, बाएं, दाएं) ईंट नहीं गिर रही है।
हम क्रमिक रूप से कुछ इरेज़र (erasures) करते हैं। प्रत्येक इरेज़र में स्थान (i, j) पर ईंट (यदि मौजूद है) गायब हो जाती है, और फिर कुछ अन्य ईंटें उस इरेज़र के कारण गिर सकती हैं। हमें प्रत्येक इरेज़र के क्रम में गिरने वाली ईंटों की संख्या दर्शाने वाला सरणी लौटाना है।
उदाहरण
इनपुट
grid = {{1,0,0,0},{1,1,1,0}}, hits = {{1,0}}
आउटपुट
[2]
व्याख्या
(1, 0) पर स्थित ईंट को हटाने पर, (1, 1) और (1, 2) पर स्थित ईंटें गिर जाएंगी। इसलिए उत्तर 2 है।
समाधान दृष्टिकोण (उल्टा प्रक्रिया - Reverse Process)
- सभी हिट्स को पहले लागू करें (ईंटें हटाएं)।
- शीर्ष पंक्ति से DFS करके स्थिर ईंटों (जो नहीं गिरेंगी) को चिह्नित करें (मान 2 से)।
- हिट्स को उल्टे क्रम में प्रक्रिया करें: ईंट को वापस जोड़ें।
- यदि जोड़ी गई ईंट शीर्ष से जुड़ी नहीं है, तो उससे DFS करके गिरने वाली ईंटों की गणना करें।
- परिणामों को उल्टा करके मूल क्रम में लौटाएं।
कार्यकारी प्रोग्राम
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
int dfs(int i, int j, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1)
return 0;
int ret = 1;
grid[i][j] = 2; // स्थिर ईंट के रूप में चिह्नित
for (int k = 0; k < 4; k++) {
ret += dfs(i + dir[k][0], j + dir[k][1], grid);
}
return ret;
}
bool notConnected(int x, int y, vector<vector<int>>& grid) {
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid[0].size())
continue;
if (grid[nx][ny] == 2)
return false; // शीर्ष से जुड़ी है
}
return x == 0; // शीर्ष पंक्ति में है
}
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
vector<int> ret;
// सभी हिट्स लागू करें
for (int i = 0; i < hits.size(); i++) {
grid[hits[i][0]][hits[i][1]] -= 1;
}
// शीर्ष से स्थिर ईंटें चिह्नित करें
for (int i = 0; i < grid[0].size(); i++) {
dfs(0, i, grid);
}
// हिट्स को उल्टे क्रम में प्रक्रिया करें
reverse(hits.begin(), hits.end());
for (int i = 0; i < hits.size(); i++) {
int x = hits[i][0];
int y = hits[i][1];
grid[x][y] += 1; // ईंट वापस जोड़ें
if (grid[x][y] == 1 && notConnected(x, y, grid)) {
ret.push_back(dfs(x, y, grid) - 1); // स्वयं को घटाएं
} else {
ret.push_back(0);
}
}
reverse(ret.begin(), ret.end());
return ret;
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{1,1,1,0}};
vector<vector<int>> v1 = {{1,0}};
print_vector(ob.hitBricks(v, v1));
return 0;
}
आउटपुट
[2, ]
