सी ++ में हिट होने पर ईंटें गिरती हैं

मान लीजिए कि हमारे पास बाइनरी मानों (0s और 1s) का ग्रिड है, सेल में 1s ईंटों का प्रतिनिधित्व करते हैं। इन शर्तों को पूरा करने पर एक ईंट नहीं गिरेगी -

• कोई भी ईंट सीधे ग्रिड के शीर्ष से जुड़ी होती है

• या इसके कम से कम एक आसन्न (ऊपर, नीचे, बाएँ, दाएँ) ईंटें नहीं गिरेंगी।

हम क्रमिक रूप से कुछ मिटाने का काम करेंगे। प्रत्येक मामले में हम स्थान (i, j) पर मिटाना चाहते हैं, उस स्थान पर ईंट (यदि वह मौजूद है) गायब हो जाएगी, और फिर उस क्षरण के कारण कुछ अन्य ईंटें गिर सकती हैं। हमें क्रम में प्रत्येक मिटाने के बाद गिरने वाली ईंटों की संख्या का प्रतिनिधित्व करने वाली सरणी ढूंढनी होगी।

इसलिए, यदि इनपुट ग्रिड =[[1,0,0,0,0], [1,1,1,0]] और हिट =[[1,0]] की तरह है, तो आउटपुट [2] होगा, इसका कारण यह है कि यदि हम (1, 0) पर रखी ईंट को हटा दें, तो (1, 1) और (1, 2) की ईंट गिर जाएगी। इसलिए हमें 2 लौटना चाहिए।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आकार की एक सरणी डीआईआर परिभाषित करें:4 x 2, डीआईआर:={{1, 0}, {- 1, 0}, {0, 1}, {0, - 1}}

• फ़ंक्शन dfs() को परिभाषित करें, इसमें i, j, ग्रिड,

  . लगेगा

• अगर (i,j) ग्रिड क्षेत्र के अंदर हैं और ग्रिड[i, j] 1 के बराबर नहीं है, तो−

  • वापसी 0

• रिट :=1

• ग्रिड [i, j] :=2

• इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -

  • रिट:=रिट + डीएफएस (आई + डीआईआर [के, 0], जे + डीआईआर [के, 1], ग्रिड)

• वापसी रिट

• नॉटकनेक्टेड () फ़ंक्शन को परिभाषित करें, इसमें x, y और ग्रिड लगेगा,

• इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -

  • एनएक्स:=एक्स + डीआईआर [के, 0], एनवाई:=वाई + डीआईआर [के, 1]

  • अगर (एनएक्स, एनवाई) ग्रिड की सीमा में है, तो -

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • अगर ग्रिड [एनएक्स, एनवाई] 2 के समान है, तो -

    • सही लौटें

• जब x 0 के समान हो, तो सही लौटें

• मुख्य विधि से, निम्न कार्य करें -

• एक सरणी रिट परिभाषित करें

• इनिशियलाइज़ i :=0 के लिए, जब i <हिट का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -

  • ग्रिड [हिट [i, 0], हिट [i, 1]]:=ग्रिड [हिट [i, 0], हिट [i, 1]] - 1

• इनिशियलाइज़ करने के लिए i :=0, जब i <ग्रिड का आकार, अपडेट (i 1 से बढ़ाएँ), करें -

  • dfs(0, i, ग्रिड)

• सरणी हिट को उलट दें

• इनिशियलाइज़ i :=0 के लिए, जब i <हिट का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -

  • x:=हिट[i, 0], y:=हिट[i, 1]

  • यदि ग्रिड [x, y] 1 के समान है और कनेक्टेड (x, y, ग्रिड) नहीं है, तो -

    • रिट के अंत में dfs(x, y, grid) डालें

  • अन्यथा

    • रिट के अंत में 0 डालें

• सरणी को उलट दें रिट

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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 true;
         }
      }
      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.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;
   }
};
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));
}

इनपुट

{{1,0,0,0},{1,1,1,0}}, {{1,0}}

आउटपुट

[2, ]