C++-এ ইট পড়ে যাওয়ার সমস্যা (Bricks Falling When Hit) সমাধান

ধরুন আমাদের একটি বাইনারি গ্রিড দেওয়া আছে যেখানে ১ উপস্থাপন করে ইট। একটি ইট পড়ে না যদি:

সেটি সরাসরি গ্রিডের উপরের সারির সাথে সংযুক্ত থাকে, অথবা
সেটির কমপক্ষে একটি প্রতিবেশী (উপর, নিচ, বাম, ডান) ইট পড়ে না।

আমরা ক্রমাগত কিছু ইট মুছে ফেলব (erasure)। প্রতিটি মুছে ফেলার পর কতগুলো ইট পড়ে যাবে তা বের করতে হবে।

উদাহরণ

ইনপুট: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]] → আউটপুট: [2]

ব্যাখ্যা: (1, 0) পজিশনের ইট সরালে (1, 1) এবং (1, 2) পজিশনের ইট দুটি পড়ে যায়।

সমাধানের ধাপসমূহ

প্রথমে সকল hits প্রয়োগ করে গ্রিড আপডেট করুন।
গ্রিডের উপরের সারি থেকে DFS করে স্থিতিশীল ইটগুলো চিহ্নিত করুন (মান ২ দিন)।
hits-কে উল্টো দিক থেকে প্রসেস করুন (ইট যোগ করুন)।
প্রতিটি যোগ করা ইটের জন্য, যদি সেটি স্থিতিশীল না থাকে তবে 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));
}

ইনপুট

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

আউটপুট

[2, ]