C++ এ আঘাত করলে ইট পড়ে

ধরুন আমাদের কাছে বাইনারি মানের একটি গ্রিড আছে (0 এবং 1s) একটি ঘরে 1s ইটগুলিকে উপস্থাপন করে। একটি ইট যখন এই শর্তগুলিকে সন্তুষ্ট করে −

• হয় ইট সরাসরি গ্রিডের শীর্ষের সাথে সংযুক্ত থাকে

• অথবা তার সংলগ্ন (উপর, নীচে, বাম, ডান) ইটগুলির মধ্যে অন্তত একটি নামবে না৷

আমরা পর্যায়ক্রমে কিছু মুছে ফেলব। প্রতিটি ক্ষেত্রে আমরা অবস্থানে (i, j) মুছে ফেলতে চাই, সেই অবস্থানের ইট (যদি তা উপস্থিত থাকে) অদৃশ্য হয়ে যাবে, এবং তারপরে সেই মুছে ফেলার কারণে অন্য কিছু ইট পড়ে যেতে পারে। আমাদের ক্রমানুসারে প্রতিটি মুছে ফেলার পরে যে ইটের সংখ্যা ড্রপ হবে তা প্রতিনিধিত্ব করে এমন অ্যারে খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট হয় গ্রিড =[[1,0,0,0],[1,1,1,0]] এবং হিট =[[1,0]], তাহলে আউটপুট হবে [2], কারণ যদি আমরা (1, 0) তে রাখা ইটটি সরিয়ে ফেলি তবে (1, 1) এবং (1, 2) তে থাকা ইটটি নেমে যাবে। তাই আমাদের 2 ফিরে আসা উচিত।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আকারের একটি অ্যারে ডিআইর সংজ্ঞায়িত করুন:4 x 2, dir :={{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}}

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি i, j, গ্রিড,

  লাগবে

• যদি (i,j) গ্রিড অঞ্চলের ভিতরে থাকে এবং গ্রিড[i, j] 1 এর সমান না হয়, তাহলে−

  • রিটার্ন 0

• ret :=1

• গ্রিড[i, j] :=2

• আরম্ভ করার জন্য k :=0, যখন k <4, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −

  • ret :=ret + dfs(i + dir[k, 0], j + dir[k, 1], grid)

• রিটার্ন রিটার্ন

• একটি ফাংশন সংজ্ঞায়িত করুন notConnected(), এটি x, y, এবং গ্রিড নেবে,

• আরম্ভ করার জন্য k :=0, যখন k <4, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −

  • nx :=x + dir[k, 0], ny :=y + dir[k, 1]

  • যদি (nx, ny) গ্রিডের পরিসরে থাকে, তাহলে −

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • যদি গ্রিড[nx, ny] 2 এর মত হয়, তাহলে −

    • প্রত্যাবর্তন সত্য

• যখন x 0

  এর মত হয় তখন true রিটার্ন করুন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• একটি অ্যারে ret সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i <হিটের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • গ্রিড[হিট[i, 0], হিট[i, 1]] :=গ্রিড[হিট[i, 0], হিট[i, 1]] - 1

• আরম্ভ করার জন্য i :=0, যখন i <গ্রিডের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • dfs(0, i, grid)

• অ্যারে হিটগুলি বিপরীত করুন

• আরম্ভ করার জন্য i :=0, যখন i <হিটের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • x :=হিট[i, 0], y :=হিট[i, 1]

  • যদি গ্রিড[x, y] 1 এর মতো হয় এবং সংযুক্ত না হয় (x, y, গ্রিড), তাহলে −

    • ret

      এর শেষে dfs(x, y, grid) সন্নিবেশ করান

  • অন্যথায়

    • ret এর শেষে 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, ]