อิฐตกเมื่อถูกตีใน C++

สมมติว่าเรามีกริดค่าบายนารี (0 และ 1) โดย 1 แทนอิฐ อิฐจะไม่ตกหากตรงตามเงื่อนไข − อยู่ติดขอบบนของกริดโดยตรง หรือมีอิฐติดกัน (บน, ล่าง, ซ้าย, ขวา) อย่างน้อยหนึ่งก้อนที่ไม่ตก

เราจะทำการลบอิฐตามลำดับ ในแต่ละครั้งลบอิฐที่ตำแหน่ง (i, j) อิฐที่อยู่ที่นั่นจะหายไป และอิฐอื่นอาจตกตามมา เราต้องหาเมทริกซ์ที่แสดงจำนวนอิฐที่ตกหลังการลบแต่ละครั้ง

เช่น grid = [[1,0,0,0],[1,1,1,0]] และ hits = [[1,0]] เอาต์พุตคือ [2] เพราะลบอิฐที่ (1,0) อิฐที่ (1,1) และ (1,2) จะตก

วิธีแก้ − ใช้ DFS ย้อนกลับจากการลบ ทำ Reverse Process โดยเพิ่มอิฐกลับไปทีละก้อน

ตัวอย่าง

#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], 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, ]