srm297 div1 p2

#include <iostream>
#include <vector>
#include <string>
using namespace std;


struct Coord {
    int l, c;
    Coord()
    {
        l = c = 0;
    }
    Coord(int l, int c)
    {
        this->l = l;
        this->c = c;
    }
};


class CageTheMonster {

    public:
    typedef vector<string> vs_t;
    typedef vector<int> vi_t;
    typedef vector<vi_t> vv_t;
    typedef vector<Coord> vC_t;
    vv_t mat; // 0-clear/put 1-wall/ff 3-monster
    vC_t pos; // start places
    int cnt;
    bool escaped;
    Coord start; // start pos

    int get_nr(char x)
    {
        switch (x) {
            case '.': return 0;
            case '#': return 1;
            case 'F': return 1; // not used
            case '^': return 2;
        }
        return -1;
    }

    bool on_margin(const Coord& tmp)
    {
        if (tmp.l == 0 || tmp.l == mat.size() - 1 || tmp.c == 0 || tmp.c == mat[0].size() - 1) return true;
        return false;
    }

    void escape(int l, int c)
    {
        if (mat[l][c] == 1 || mat[l][c] == 3 || escaped) return; // blocked, already explored or escaped
        if (on_margin(Coord(l, c))) {
            escaped = true;
            return;
        }
        mat[l][c] = 3; // mark place
        escape(l + 1, c);
        escape(l - 1, c);
        escape(l, c + 1);
        escape(l, c - 1);
        mat[l][c] = 0; // availability purpose
    }

    void test()
    {
        /// Show `mat` at a certain state.
        for (int i = 0; i < mat.size(); ++i) {
            for (int j = 0; j < mat[0].size(); ++j) cout << mat[i][j];
            cout << endl;
        }
    }

    void back(int force) /* N^7 (the impossible worst) */
    {
        if (force == cnt) return;
        escaped = false;
        escape(start.l, start.c);
        if (!escaped) {
            cnt = force;
            return;
        }
        for (int i = 0; i < mat.size() && force + 1 < cnt; ++i) {
            // pick a force field path
            vi_t section; // backup path
            if (i != start.l) { // Ox
                section = mat[i]; // copy last path
                mat[i] = vi_t(mat[0].size(), 1); // fill path
                //if (force == 0 && i == 3) test();
                back(force + 1);
                mat[i] = section;
            }
        }
        for (int i = 0; i < mat[0].size() && force + 1 < cnt; ++i) {
            // pick a force field path
            vi_t section; // backup path
            if (i != start.c) { // Oy
                section.clear(); // same shit here
                for (int j = 0; j < mat.size(); ++j) {
                    section.push_back(mat[j][i]);
                    mat[j][i] = 1;
                }
                back(force + 1);
                for (int j = 0; j < mat.size(); ++j) {
                    mat[j][i] = section[j];
                }
            }
        }
    }

    int capture(vs_t lab)
    {
        cnt = 4; // init
        // make int mat
        mat.resize(lab.size());
        for (int i = 0; i < mat.size(); ++i) {
            mat[i].resize(lab[0].size());
            for (int j = 0; j < mat[0].size(); ++j) {
                mat[i][j] = get_nr(lab[i][j]);
                // save possible places
                if (mat[i][j] == 2) {
                    pos.push_back(Coord(i, j));
                    mat[i][j] = 0;
                }
            }
        }
        // get rid of margins
        vC_t tmp; // temp vec
        for (int i = 0; i < pos.size(); ++i) {
            if (!on_margin(pos[i])) tmp.push_back(pos[i]);
        }
        pos = tmp;
        if (!pos.size()) return -1; // impossible
        for (int i = 0; i < pos.size(); ++i) {
            start = pos[i];
            back(0);
        }
        return cnt;
    }
};