SRM297-D1-500 CageTheMonster

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

class CageTheMonster{
    public:
    char graph[40][40];
    char graph_orig[40][40];
    vector<pair<int,int>> p_start;
    int n,m;
    queue<pair<int,int>> q;
    map<pair<int,int>,int> vis;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,-1,1};

    int update(int x, pair<int,int> start) {
        int ret = 0;
        if(x & 1) {
            if(start.first < n-1) {
                ret++;
                for(int i = 0; i < m; i++) {
                    graph[start.first+1][i] = '#';
                }
            }
        }
        if(x & 2) {
            if(start.first > 0) {
                ret++;
                for(int i = 0; i < m; i++) {
                    graph[start.first-1][i] = '#';
                }
            }
        }
        if(x & 4) {
            if(start.second < m-1) {
                ret++;
                for(int i = 0; i < n; i++) {
                    graph[i][start.second+1] = '#';
                }
            }
        }
        if(x & 8) {
            if(start.second > 0) {
                ret++;
                for(int i = 0; i < n; i++) {
                    graph[i][start.second-1] = '#';
                }
            }
        }
        return ret;
    }

    void remove_update(int x, pair<int,int> start) {
        if(x & 1) {
            if(start.first < n-1) {
                for(int i = 0; i < m; i++) {
                    graph[start.first+1][i] = graph_orig[start.first+1][i];
                }
            }
        }
        if(x & 2) {
            if(start.first > 0) {
                for(int i = 0; i < m; i++) {
                    graph[start.first-1][i] = graph_orig[start.first-1][i];
                }
            }
        }
        if(x & 4) {
            if(start.second < m-1) {
                for(int i = 0; i < n; i++) {
                    graph[i][start.second+1] = graph_orig[i][start.second+1];
                }
            }
        }
        if(x & 8) {
            if(start.second > 0) {
                for(int i = 0; i < n; i++) {
                    graph[i][start.second-1] = graph_orig[i][start.second-1];
                }
            }
        }
    }

    int possible(pair<int,int> p) {
        if(p.first < 0 || p.first >= n || p.second < 0 || p.second >= m) {
            return 2;
        }
        return (graph[p.first][p.second] != '#' && !vis[p]);
    }

    bool bfs(pair<int,int> start) {
        while(!q.empty())
            q.pop();
        vis.clear();
        q.push(start);
        vis[start] = 1;
        while(!q.empty()) {
            pair<int,int> curr = q.front();
            q.pop();
            for(int i = 0; i < 4; i++) {
                pair<int,int> nxt = {curr.first+dx[i],curr.second+dy[i]};
                int poss = possible(nxt);
                if(poss == 2) {
                    return true;
                }
                if(poss) {
                    vis[nxt] = true;
                    q.push(nxt);
                }
            }
        }
        return false;
    }

    int capture(vector <string> labyrinth) {
        n = labyrinth.size();
        m = labyrinth[0].size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                graph[i][j] = graph_orig[i][j] = labyrinth[i][j];
                if(graph[i][j] == '^') {
                    p_start.push_back({i,j});
                }
            }
        }
        int mn = -1;
        for(int i = 0; i < 16; i++) {
            for(pair<int,int> start : p_start) {
                int cost = update(i,start);
                if(!bfs(start)) {
                    mn = (mn == -1 ? cost:min(mn,cost));
                }
                remove_update(i,start);
            }
        }
        return mn;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}