#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second #include "osalib.h" const int N = 1010; int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0}; int n,m; int vis[N][N]; char bo[N][N]; vector<pii> osady; int color; int ids[N][N]; int moved; int bad[N][N]; void NowaWyspa(int n_, int m_, char **board) { n=n_; m=m_; FOR(i,n+2) FOR(j,m+2) bo[i][j] = 'W'; FOR(i,n) FOR(j,m) bo[i+1][j+1] = board[i][j]; FORI(i,n) FORI(j,m) if (bo[i][j] == 'K') { ids[i][j] = SZ(osady); osady.pb(mp(i,j)); } moved = 1; } int NowaWarownia(int r, int c) { if (bad[r][c] == moved) { return 0; } color++; bo[r][c] = 'W'; queue<int> q; q.push(osady[0].fi); q.push(osady[0].se); vis[osady[0].fi][osady[0].se] = color; int need = SZ(osady)-1; while (!q.empty()) { if (need == 0) break; int x = q.front(); q.pop(); int y = q.front(); q.pop(); FOR(k,4) { int nx = x+dx[k], ny = y+dy[k]; if (vis[nx][ny] == color) continue; if (bo[nx][ny] == 'W') continue; if (bo[nx][ny] == 'K') need--; q.push(nx); q.push(ny); vis[nx][ny] = color; } } if (need == 0) { return 1; } else { bad[r][c] = moved; bo[r][c] = '.'; return 0; } } void PrzeniesOsade(int r1, int c1, int r2, int c2) { int id = ids[r1][c1]; osady[id] = mp(r2,c2); bo[r1][c1] = '.'; bo[r2][c2] = 'K'; ids[r2][c2] = id; moved++; }
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 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second #include "osalib.h" const int N = 1010; int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0}; int n,m; int vis[N][N]; char bo[N][N]; vector<pii> osady; int color; int ids[N][N]; int moved; int bad[N][N]; void NowaWyspa(int n_, int m_, char **board) { n=n_; m=m_; FOR(i,n+2) FOR(j,m+2) bo[i][j] = 'W'; FOR(i,n) FOR(j,m) bo[i+1][j+1] = board[i][j]; FORI(i,n) FORI(j,m) if (bo[i][j] == 'K') { ids[i][j] = SZ(osady); osady.pb(mp(i,j)); } moved = 1; } int NowaWarownia(int r, int c) { if (bad[r][c] == moved) { return 0; } color++; bo[r][c] = 'W'; queue<int> q; q.push(osady[0].fi); q.push(osady[0].se); vis[osady[0].fi][osady[0].se] = color; int need = SZ(osady)-1; while (!q.empty()) { if (need == 0) break; int x = q.front(); q.pop(); int y = q.front(); q.pop(); FOR(k,4) { int nx = x+dx[k], ny = y+dy[k]; if (vis[nx][ny] == color) continue; if (bo[nx][ny] == 'W') continue; if (bo[nx][ny] == 'K') need--; q.push(nx); q.push(ny); vis[nx][ny] = color; } } if (need == 0) { return 1; } else { bad[r][c] = moved; bo[r][c] = '.'; return 0; } } void PrzeniesOsade(int r1, int c1, int r2, int c2) { int id = ids[r1][c1]; osady[id] = mp(r2,c2); bo[r1][c1] = '.'; bo[r2][c2] = 'K'; ids[r2][c2] = id; moved++; } |