1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>

#include "osalib.h"

#define ALL(X)        X.begin(),X.end()
#define FOR(I,A,B)    for(int (I) = (A); (I) <= (B); (I)++)
#define FORW(I,A,B)   for(int (I) = (A); (I) < (B);  (I)++)
#define FORD(I,A,B)   for(int (I) = (A); (I) >= (B); (I)--)
#define CLEAR(X)      memset(X,0,sizeof(X))
#define SIZE(X)       int(X.size())
#define CONTAINS(A,X) (A.find(X) != A.end())
#define PB            push_back
#define MP            make_pair
#define X             first
#define Y             second
using namespace std;
template<typename T, typename U> ostream& operator << (ostream& os, const pair<T, U> &_p) { return os << "(" << _p.X << "," << _p.Y << ")"; }
template<typename T> ostream& operator << (ostream &os, const vector<T>& _V) { bool f = true; os << "["; for(auto v: _V) { os << (f ? "" : ",") << v; f = false; } return os << "]"; }
template<typename T> ostream& operator << (ostream &os, const set<T>& _S) { bool f = true; os << "("; for(auto s: _S) { os << (f ? "" : ",") << s; f = false; } return os << ")"; }
template<typename T, typename U> ostream& operator << (ostream &os, const map<T, U>& _M) { return os << set<pair<T, U>>(ALL(_M)); }
typedef signed long long slong;
typedef long double ldouble;
typedef pair<int,int> pii;
const slong INF = 1000000100;
const ldouble EPS = 1e-9;

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int MAXN = 1042;

int wyspa[MAXN+42][MAXN+42];
/// 0 - zajete (warownia lub brzeg)
/// 1 - tereny rolne
/// 2 - osada
int N, M;
int dfs_cnt;
int vis[MAXN+42][MAXN+42];

int kod(char c) {
    if(c == '.') return 1;
    if(c == 'K') return 2;
    return 0;
}

void NowaWyspa(int n, int m, char **Board) {
    N = n;
    M = m;
    FOR(i,1,N) {
        FOR(j,1,M) {
            char c = Board[i-1][j-1];
            wyspa[i][j] = kod(c);
        }
    }
    dfs_cnt = 0;
}

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

int dfs(int r, int c) {
    /// zwraca w ilu poddrzewach dfs sa osady
    /// +1 jesli (r,c) to osada, ale to nie przeszkadza
    vis[r][c] = dfs_cnt;
    int dzieci = 0;
    if(wyspa[r][c] == 2) {
        dzieci = 1;
    }

    FORW(i,0,4) {
        int x = r + dx[i];
        int y = c + dy[i];
        if(!wyspa[x][y]) continue;
        if(vis[x][y] == dfs_cnt) continue;
        int d = dfs(x,y);
        if(d > 0) {
            dzieci++;
        }
    }

    return dzieci;
}

int NowaWarownia(int r, int c) {
    dfs_cnt++;
    /*FOR(i,1,N) {
        FOR(j,1,M) cout << wyspa[i][j] << " ";
        cout << "\n";
    }
    cout << endl;*/
    if(dfs(r,c) > 1) {
        /// wiecej niz jedno dziecko z osadami w drzewie dfs
        /// => punkt arykulacji
        return 0;
    }
    wyspa[r][c] = 0;
    return 1;
}

void PrzeniesOsade(int r1, int c1, int r2, int c2) {
    wyspa[r1][c1] = 1;
    wyspa[r2][c2] = 2;
}