#include <iostream>
#include <vector>

using std::vector;

using std::cout;
using std::endl;

class Solution {
public:
    int containVirus(vector<vector<int>> &grid) {
        int walls = 0;
        do {
            walls += build_wall(grid);
        } while (spread(grid));
        return walls;
    }

private:
    int build_wall(vector<vector<int>> &grid) {
        bool flag[grid.size()][grid[0].size()];
        memset(flag, 0, sizeof(flag));
        
        return 0;
    }

    bool spread(vector<vector<int>> &grid) {
        for (int i = 0; i < grid.size(); i++) {
            vector<int> &col = grid[i];
            for (int j = 0; j < col.size(); j++) {
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 0 || grid.size() <= x || y < 0 || col.size() <= y) continue;
                    if (grid[x][y] == 1 && grid[i][j] == 0) grid[i][j] = -1;
                }
            }
        }
        int cnt = 0;
        for (vector<int> &col : grid) {
            for (int &row : col) {
                if (row == -1) {
                    row = 1;
                    cnt++;
                }
            }
        }
        return 0 < cnt;
    }

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};
};

int main() {
    vector<vector<int>> grid =
        {{1, 1, 1, 0, 0, 0, 0, 0, 0},
         {1, 0, 1, 0, 1, 1, 1, 1, 1},
         {1, 1, 1, 0, 0, 0, 0, 0, 0}};
    Solution* sol = new Solution();
    
    cout << "actual: " << sol->containVirus(grid) << ", expected: " << 13 << endl;

    return 0;
}