http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp17Day2&pid=F

rupc2017day2F.cpp

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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

class UnionFind {
private:
    const int n;
    vector<int> uni;
public:
    UnionFind(int _n) : n(_n), uni(_n, -1) {}
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
        return true;
    }
    int getSize(int x) {
        return -uni[root(x)];
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

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

int n, m, k;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> n >> m >> k;
    map<Pii, int> mp;
    rep(i, k) {
        int x, y;
        cin >> x >> y;
        mp[Pii(x, y)];
    }

    for(int y = -1; y <= m; ++y) {
        if (y >= 2) {
            mp[Pii(-1, y)];
        }
        if (y <= m - 3) {
            mp[Pii(n, y)];
        }
    }

    for(int x = -1; x <= n; ++x) {
        if (x >= 2) {
            mp[Pii(x, -1)];
        }
        if (x <= n - 3) {
            mp[Pii(x, m)];
        }
    }

    int num = 0;
    for (auto& pp : mp) {
        pp.second = num++;
    }
    const int s = num, t = num + 1;
    const Pii ps = Pii(111111, 111111), pt = Pii(999999, 999999);
    mp[ps] = s;
    mp[pt] = t;
    num += 2;

    UnionFind uf(num);
    for (auto pp : mp) {
        int x, y;
        tie(x, y) = pp.first;
        int id = pp.second;
        if (x == -1 || y == m) {
            uf.unite(id, s);
        }
        if (x == n || y == -1) {
            uf.unite(id, t);
        }
        rep(k, 8) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (mp.count(Pii(nx, ny))) {
                int nid = mp[Pii(nx, ny)];
                uf.unite(id, nid);
            }
        }
    }

    int ans = 2;
    if (uf.same(s, t)) {
        ans = 0;
    }
    else {
        [&](){
            for (auto pp : mp) {
                int x, y;
                tie(x, y) = pp.first;
                int id = pp.second;
                if (!uf.same(id, s) && !uf.same(id, t)) continue;
                for (int nx = x - 2; nx <= x + 2; nx++) {
                    for (int ny = y - 2; ny <= y + 2; ny++) {
                        if (abs(nx - x) != 2 && abs(ny - y) != 2) continue;
                        if (!mp.count(Pii(nx, ny))) continue;
                        int nid = mp[Pii(nx, ny)];
                        if (!uf.same(nid, s) && !uf.same(nid, t)) continue;
                        if (!uf.same(id, nid)) {
                            ans = 1;
                            return;
                        }
                    }
                }
            }
        }();
    }

    cout << ans << endl;
}