#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; }
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; } |