0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 75 73 69 6e 67 20 6e 61 6d sert>..using nam
0140: 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 79 70 espace std;..typ
0150: 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 20 4c edef long long L
0160: 4c 3b 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 L;..typedef long
0170: 20 64 6f 75 62 6c 65 20 4c 44 3b 0d 0a 74 79 70 double LD;..typ
0180: 65 64 65 66 20 63 6f 6d 70 6c 65 78 3c 64 6f 75 edef complex<dou
0190: 62 6c 65 3e 20 43 4d 50 3b 0d 0a 0d 0a 63 6f 6e ble> CMP;....con
01a0: 73 74 20 69 6e 74 20 64 79 5b 5d 20 3d 20 7b 2d st int dy[] = {-
01b0: 31 2c 2b 31 2c 30 2c 30 7d 3b 0d 0a 63 6f 6e 73 1,+1,0,0};..cons
01c0: 74 20 69 6e 74 20 64 78 5b 5d 20 3d 20 7b 30 2c t int dx[] = {0,
01d0: 30 2c 2d 31 2c 2b 31 7d 3b 0d 0a 0d 0a 74 65 6d 0,-1,+1};....tem
01e0: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 plate<typename T
01f0: 3e 0d 0a 63 6c 61 73 73 20 49 64 47 65 6e 0d 0a >..class IdGen..
0200: 7b 0d 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 3e 20 {...map<T, int>
0210: 76 32 69 64 5f 3b 0d 0a 09 76 65 63 74 6f 72 3c v2id_;...vector<
0220: 54 3e 20 20 20 69 64 32 76 5f 3b 0d 0a 70 75 62 T> id2v_;..pub
0230: 6c 69 63 3a 0d 0a 09 69 6e 74 20 76 32 69 64 28 lic:...int v2id(
0240: 63 6f 6e 73 74 20 54 26 20 76 29 20 7b 0d 0a 09 const T& v) {...
0250: 09 69 66 28 20 21 76 32 69 64 5f 2e 63 6f 75 6e .if( !v2id_.coun
0260: 74 28 76 29 20 29 20 7b 20 76 32 69 64 5f 5b 76 t(v) ) { v2id_[v
0270: 5d 20 3d 20 73 69 7a 65 28 29 3b 20 69 64 32 76 ] = size(); id2v
0280: 5f 2e 70 75 73 68 5f 62 61 63 6b 28 76 29 3b 20 _.push_back(v);
0290: 7d 0d 0a 09 09 72 65 74 75 72 6e 20 76 32 69 64 }....return v2id
02a0: 5f 5b 76 5d 3b 0d 0a 09 7d 0d 0a 09 63 6f 6e 73 _[v];...}...cons
02b0: 74 20 54 26 20 69 64 32 76 28 69 6e 74 20 69 29 t T& id2v(int i)
02c0: 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 const { return
02d0: 69 64 32 76 5f 5b 69 5d 3b 20 7d 0d 0a 09 69 6e id2v_[i]; }...in
02e0: 74 20 73 69 7a 65 28 29 20 63 6f 6e 73 74 20 7b t size() const {
02f0: 20 72 65 74 75 72 6e 20 69 64 32 76 5f 2e 73 69 return id2v_.si
0300: 7a 65 28 29 3b 20 7d 0d 0a 7d 3b 0d 0a 0d 0a 74 ze(); }..};....t
0310: 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 emplate<typename
0320: 20 56 65 72 74 2c 20 74 79 70 65 6e 61 6d 65 20 Vert, typename
0330: 46 6c 6f 77 2c 20 69 6e 74 20 4e 56 3d 32 30 34 Flow, int NV=204
0340: 38 3e 0d 0a 63 6c 61 73 73 20 4d 61 78 46 6c 6f 8>..class MaxFlo
0350: 77 0d 0a 7b 0d 0a 09 49 64 47 65 6e 3c 56 65 72 w..{...IdGen<Ver
0360: 74 3e 20 69 64 67 65 6e 3b 0d 0a 09 76 65 63 74 t> idgen;...vect
0370: 6f 72 3c 69 6e 74 3e 20 47 5b 4e 56 5d 3b 0d 0a or<int> G[NV];..
0380: 09 46 6c 6f 77 20 46 5b 4e 56 5d 5b 4e 56 5d 3b .Flow F[NV][NV];
0390: 0d 0a 0d 0a 70 75 62 6c 69 63 3a 0d 0a 09 76 6f ....public:...vo
03a0: 69 64 20 61 64 64 45 64 67 65 28 20 56 65 72 74 id addEdge( Vert
03b0: 20 73 5f 2c 20 56 65 72 74 20 74 5f 2c 20 46 6c s_, Vert t_, Fl
03c0: 6f 77 20 66 20 29 0d 0a 09 7b 0d 0a 09 09 63 6f ow f )...{....co
03d0: 6e 73 74 20 69 6e 74 20 73 20 3d 20 69 64 67 65 nst int s = idge
03e0: 6e 2e 76 32 69 64 28 73 5f 29 2c 20 74 20 3d 20 n.v2id(s_), t =
03f0: 69 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0d idgen.v2id(t_);.
0400: 0a 09 09 47 5b 73 5d 2e 70 75 73 68 5f 62 61 63 ...G[s].push_bac
0410: 6b 28 74 29 3b 0d 0a 09 09 47 5b 74 5d 2e 70 75 k(t);....G[t].pu
0420: 73 68 5f 62 61 63 6b 28 73 29 3b 0d 0a 09 09 46 sh_back(s);....F
0430: 5b 73 5d 5b 74 5d 20 3d 20 66 3b 0d 0a 09 09 46 [s][t] = f;....F
0440: 5b 74 5d 5b 73 5d 20 3d 20 30 3b 0d 0a 09 7d 0d [t][s] = 0;...}.
0450: 0a 0d 0a 09 46 6c 6f 77 20 63 61 6c 63 28 20 56 ....Flow calc( V
0460: 65 72 74 20 73 5f 2c 20 56 65 72 74 20 74 5f 20 ert s_, Vert t_
0470: 29 0d 0a 09 7b 0d 0a 09 09 63 6f 6e 73 74 20 69 )...{....const i
0480: 6e 74 20 53 20 3d 20 69 64 67 65 6e 2e 76 32 69 nt S = idgen.v2i
0490: 64 28 73 5f 29 2c 20 44 20 3d 20 69 64 67 65 6e d(s_), D = idgen
04a0: 2e 76 32 69 64 28 74 5f 29 3b 0d 0a 09 09 66 6f .v2id(t_);....fo
04b0: 72 28 20 46 6c 6f 77 20 74 6f 74 61 6c 3d 30 20 r( Flow total=0
04c0: 3b 3b 20 29 20 7b 0d 0a 09 09 09 2f 2f 20 44 6f ;; ) {.....// Do
04d0: 20 42 46 53 20 61 6e 64 20 63 6f 6d 70 75 74 65 BFS and compute
04e0: 20 74 68 65 20 6c 65 76 65 6c 20 66 6f 72 20 65 the level for e
04f0: 61 63 68 20 6e 6f 64 65 2e 0d 0a 09 09 09 69 6e ach node......in
0500: 74 20 4c 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b 0d t LV[NV] = {0};.
0510: 0a 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 ....vector<int>
0520: 51 28 31 2c 20 53 29 3b 0d 0a 09 09 09 66 6f 72 Q(1, S);.....for
0530: 28 69 6e 74 20 6c 76 3d 31 3b 20 21 51 2e 65 6d (int lv=1; !Q.em
0540: 70 74 79 28 29 3b 20 2b 2b 6c 76 29 20 7b 0d 0a pty(); ++lv) {..
0550: 09 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 ....vector<int>
0560: 51 32 3b 0d 0a 09 09 09 09 66 6f 72 28 73 69 7a Q2;......for(siz
0570: 65 5f 74 20 69 3d 30 3b 20 69 21 3d 51 2e 73 69 e_t i=0; i!=Q.si
0580: 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 ze(); ++i) {....
0590: 09 09 09 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c ...const vector<
05a0: 69 6e 74 3e 26 20 6e 65 20 3d 20 47 5b 51 5b 69 int>& ne = G[Q[i
05b0: 5d 5d 3b 0d 0a 09 09 09 09 09 66 6f 72 28 73 69 ]];.......for(si
05c0: 7a 65 5f 74 20 6a 3d 30 3b 20 6a 21 3d 6e 65 2e ze_t j=0; j!=ne.
05d0: 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 0d 0a 09 09 size(); ++j)....
05e0: 09 09 09 09 69 66 28 20 46 5b 51 5b 69 5d 5d 5b ....if( F[Q[i]][
05f0: 6e 65 5b 6a 5d 5d 20 26 26 20 21 4c 56 5b 6e 65 ne[j]] && !LV[ne
0600: 5b 6a 5d 5d 20 26 26 20 6e 65 5b 6a 5d 21 3d 53 [j]] && ne[j]!=S
0610: 20 29 0d 0a 09 09 09 09 09 09 09 4c 56 5b 6e 65 ).........LV[ne
0620: 5b 6a 5d 5d 3d 6c 76 2c 20 51 32 2e 70 75 73 68 [j]]=lv, Q2.push
0630: 5f 62 61 63 6b 28 6e 65 5b 6a 5d 29 3b 0d 0a 09 _back(ne[j]);...
0640: 09 09 09 7d 0d 0a 09 09 09 09 51 2e 73 77 61 70 ...}......Q.swap
0650: 28 51 32 29 3b 0d 0a 09 09 09 7d 0d 0a 0d 0a 09 (Q2);.....}.....
0660: 09 09 2f 2f 20 44 65 73 74 69 6e 61 74 69 6f 6e ..// Destination
0670: 20 69 73 20 6e 6f 77 20 75 6e 72 65 61 63 68 61 is now unreacha
0680: 62 6c 65 2e 20 44 6f 6e 65 2e 0d 0a 09 09 09 69 ble. Done......i
0690: 66 28 20 21 4c 56 5b 44 5d 20 29 0d 0a 09 09 09 f( !LV[D] ).....
06a0: 09 72 65 74 75 72 6e 20 74 6f 74 61 6c 3b 0d 0a .return total;..
06b0: 0d 0a 09 09 09 2f 2f 20 49 74 65 72 61 74 69 6e .....// Iteratin
06c0: 67 20 44 46 53 2e 0d 0a 09 09 09 62 6f 6f 6c 20 g DFS......bool
06d0: 62 6c 6f 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b 7d blocked[NV] = {}
06e0: 3b 0d 0a 09 09 09 74 6f 74 61 6c 20 2b 3d 20 64 ;.....total += d
06f0: 69 6e 69 63 5f 64 66 73 28 20 53 2c 20 44 2c 20 inic_dfs( S, D,
0700: 4c 56 2c 20 30 78 37 66 66 66 66 66 66 66 2c 20 LV, 0x7fffffff,
0710: 62 6c 6f 63 6b 65 64 20 29 3b 0d 0a 09 09 7d 0d blocked );....}.
0720: 0a 09 7d 0d 0a 0d 0a 70 72 69 76 61 74 65 3a 0d ..}....private:.
0730: 0a 09 46 6c 6f 77 20 64 69 6e 69 63 5f 64 66 73 ..Flow dinic_dfs
0740: 28 20 69 6e 74 20 76 2c 20 69 6e 74 20 44 2c 20 ( int v, int D,
0750: 69 6e 74 20 4c 56 5b 5d 2c 20 46 6c 6f 77 20 66 int LV[], Flow f
0760: 6c 6f 77 5f 69 6e 2c 20 62 6f 6f 6c 20 62 6c 6f low_in, bool blo
0770: 63 6b 65 64 5b 5d 20 29 0d 0a 09 7b 0d 0a 09 09 cked[] )...{....
0780: 46 6c 6f 77 20 66 6c 6f 77 5f 6f 75 74 20 3d 20 Flow flow_out =
0790: 30 3b 0d 0a 09 09 66 6f 72 28 73 69 7a 65 5f 74 0;....for(size_t
07a0: 20 69 3d 30 3b 20 69 21 3d 47 5b 76 5d 2e 73 69 i=0; i!=G[v].si
07b0: 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 ze(); ++i) {....
07c0: 09 69 6e 74 20 75 20 3d 20 47 5b 76 5d 5b 69 5d .int u = G[v][i]
07d0: 3b 0d 0a 09 09 09 69 66 28 20 4c 56 5b 76 5d 2b ;.....if( LV[v]+
07e0: 31 3d 3d 4c 56 5b 75 5d 20 26 26 20 46 5b 76 5d 1==LV[u] && F[v]
07f0: 5b 75 5d 20 29 20 7b 0d 0a 09 09 09 09 46 6c 6f [u] ) {......Flo
0800: 77 20 66 20 3d 20 6d 69 6e 28 66 6c 6f 77 5f 69 w f = min(flow_i
0810: 6e 2d 66 6c 6f 77 5f 6f 75 74 2c 20 46 5b 76 5d n-flow_out, F[v]
0820: 5b 75 5d 29 3b 0d 0a 09 09 09 09 69 66 28 20 75 [u]);......if( u
0830: 3d 3d 44 20 7c 7c 20 21 62 6c 6f 63 6b 65 64 5b ==D || !blocked[
0840: 75 5d 20 26 26 20 28 66 3d 64 69 6e 69 63 5f 64 u] && (f=dinic_d
0850: 66 73 28 75 2c 44 2c 4c 56 2c 66 2c 62 6c 6f 63 fs(u,D,LV,f,bloc
0860: 6b 65 64 29 29 3e 30 20 29 20 7b 0d 0a 09 09 09 ked))>0 ) {.....
0870: 09 09 46 5b 76 5d 5b 75 5d 20 20 2d 3d 20 66 3b ..F[v][u] -= f;
0880: 0d 0a 09 09 09 09 09 46 5b 75 5d 5b 76 5d 20 20 .......F[u][v]
0890: 2b 3d 20 66 3b 0d 0a 09 09 09 09 09 66 6c 6f 77 += f;.......flow
08a0: 5f 6f 75 74 20 2b 3d 20 66 3b 0d 0a 09 09 09 09 _out += f;......
08b0: 09 69 66 28 20 66 6c 6f 77 5f 69 6e 20 3d 3d 20 .if( flow_in ==
08c0: 66 6c 6f 77 5f 6f 75 74 20 29 20 72 65 74 75 72 flow_out ) retur
08d0: 6e 20 66 6c 6f 77 5f 6f 75 74 3b 0d 0a 09 09 09 n flow_out;.....
08e0: 09 7d 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 09 .}.....}....}...
08f0: 09 62 6c 6f 63 6b 65 64 5b 76 5d 20 3d 20 28 66 .blocked[v] = (f
0900: 6c 6f 77 5f 6f 75 74 3d 3d 30 29 3b 0d 0a 09 09 low_out==0);....
0910: 72 65 74 75 72 6e 20 66 6c 6f 77 5f 6f 75 74 3b return flow_out;
0920: 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 63 6c 61 73 ...}..};....clas
0930: 73 20 42 6c 6f 63 6b 33 43 68 65 63 6b 65 72 73 s Block3Checkers
0940: 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 69 6e 74 { public:...int
0950: 20 62 6c 6f 63 6b 54 68 65 6d 28 76 65 63 74 6f blockThem(vecto
0960: 72 20 3c 73 74 72 69 6e 67 3e 20 62 6f 61 72 64 r <string> board
0970: 29 0d 0a 09 7b 0d 0a 09 09 69 6e 74 20 48 20 3d )...{....int H =
0980: 20 62 6f 61 72 64 2e 73 69 7a 65 28 29 3b 0d 0a board.size();..
0990: 09 09 69 6e 74 20 57 20 3d 20 62 6f 61 72 64 5b ..int W = board[
09a0: 30 5d 2e 73 69 7a 65 28 29 3b 0d 0a 09 09 66 6f 0].size();....fo
09b0: 72 28 69 6e 74 20 79 3d 30 3b 20 79 3c 48 3b 20 r(int y=0; y<H;
09c0: 2b 2b 79 29 0d 0a 09 09 66 6f 72 28 69 6e 74 20 ++y)....for(int
09d0: 78 3d 30 3b 20 78 3c 57 3b 20 2b 2b 78 29 0d 0a x=0; x<W; ++x)..
09e0: 09 09 09 69 66 28 62 6f 61 72 64 5b 79 5d 5b 78 ...if(board[y][x
09f0: 5d 20 3d 3d 20 27 41 27 29 20 7b 0d 0a 09 09 09 ] == 'A') {.....
0a00: 09 66 6f 72 28 69 6e 74 20 64 3d 30 3b 20 64 3c .for(int d=0; d<
0a10: 34 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 4; ++d) {.......
0a20: 69 6e 74 20 78 78 20 3d 20 78 2b 64 78 5b 64 5d int xx = x+dx[d]
0a30: 3b 0d 0a 09 09 09 09 09 69 6e 74 20 79 79 20 3d ;.......int yy =
0a40: 20 79 2b 64 79 5b 64 5d 3b 0d 0a 09 09 09 09 09 y+dy[d];.......
0a50: 69 66 28 30 3c 3d 78 78 26 26 78 78 3c 57 26 26 if(0<=xx&&xx<W&&
0a60: 30 3c 3d 79 79 26 26 79 79 3c 48 26 26 62 6f 61 0<=yy&&yy<H&&boa
0a70: 72 64 5b 79 79 5d 5b 78 78 5d 3d 3d 27 41 27 29 rd[yy][xx]=='A')
0a80: 0d 0a 09 09 09 09 09 09 72 65 74 75 72 6e 20 31 ........return 1
0a90: 30 30 3b 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 7d 00;......}.....}
0aa0: 0d 0a 0d 0a 09 09 76 65 63 74 6f 72 3c 70 61 69 ......vector<pai
0ab0: 72 3c 69 6e 74 2c 69 6e 74 3e 20 3e 20 70 73 2c r<int,int> > ps,
0ac0: 20 61 73 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 as;....for(int
0ad0: 79 3d 30 3b 20 79 3c 48 3b 20 2b 2b 79 29 0d 0a y=0; y<H; ++y)..
0ae0: 09 09 66 6f 72 28 69 6e 74 20 78 3d 30 3b 20 78 ..for(int x=0; x
0af0: 3c 57 3b 20 2b 2b 78 29 0d 0a 09 09 09 69 66 28 <W; ++x).....if(
0b00: 62 6f 61 72 64 5b 79 5d 5b 78 5d 3d 3d 27 2e 27 board[y][x]=='.'
0b10: 29 0d 0a 09 09 09 09 70 73 2e 70 75 73 68 5f 62 )......ps.push_b
0b20: 61 63 6b 28 6d 61 6b 65 5f 70 61 69 72 28 79 2c ack(make_pair(y,
0b30: 78 29 29 3b 0d 0a 09 09 09 65 6c 73 65 20 69 66 x));.....else if
0b40: 28 62 6f 61 72 64 5b 79 5d 5b 78 5d 3d 3d 27 41 (board[y][x]=='A
0b50: 27 29 0d 0a 09 09 09 09 61 73 2e 70 75 73 68 5f ')......as.push_
0b60: 62 61 63 6b 28 6d 61 6b 65 5f 70 61 69 72 28 79 back(make_pair(y
0b70: 2c 78 29 29 3b 0d 0a 0d 0a 09 09 76 65 63 74 6f ,x));......vecto
0b80: 72 3c 76 65 63 74 6f 72 3c 69 6e 74 3e 20 3e 20 r<vector<int> >
0b90: 72 66 3b 0d 0a 09 09 69 66 28 6f 6b 28 62 6f 61 rf;....if(ok(boa
0ba0: 72 64 2c 61 73 2c 72 66 29 29 0d 0a 09 09 09 72 rd,as,rf)).....r
0bb0: 65 74 75 72 6e 20 30 3b 0d 0a 09 09 66 6f 72 28 eturn 0;....for(
0bc0: 69 6e 74 20 69 3d 30 3b 20 69 3c 70 73 2e 73 69 int i=0; i<ps.si
0bd0: 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 ze(); ++i) {....
0be0: 09 69 6e 74 20 79 20 3d 20 70 73 5b 69 5d 2e 66 .int y = ps[i].f
0bf0: 69 72 73 74 3b 0d 0a 09 09 09 69 6e 74 20 78 20 irst;.....int x
0c00: 3d 20 70 73 5b 69 5d 2e 73 65 63 6f 6e 64 3b 0d = ps[i].second;.
0c10: 0a 09 09 09 62 6f 61 72 64 5b 79 5d 5b 78 5d 20 ....board[y][x]
0c20: 3d 20 27 4e 27 3b 0d 0a 09 09 09 69 66 28 6f 6b = 'N';.....if(ok
0c30: 28 62 6f 61 72 64 2c 61 73 2c 72 66 29 29 0d 0a (board,as,rf))..
0c40: 09 09 09 09 72 65 74 75 72 6e 20 31 3b 0d 0a 09 ....return 1;...
0c50: 09 09 62 6f 61 72 64 5b 79 5d 5b 78 5d 20 3d 20 ..board[y][x] =
0c60: 27 2e 27 3b 0d 0a 09 09 7d 0d 0a 09 09 69 6e 74 '.';....}....int
0c70: 20 62 65 73 74 20 3d 20 36 3b 0d 0a 09 09 66 6f best = 6;....fo
0c80: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 70 73 2e r(int i=0; i<ps.
0c90: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0d 0a 09 09 size(); ++i)....
0ca0: 66 6f 72 28 69 6e 74 20 6b 3d 69 2b 31 3b 20 6b for(int k=i+1; k
0cb0: 3c 70 73 2e 73 69 7a 65 28 29 3b 20 2b 2b 6b 29 <ps.size(); ++k)
0cc0: 20 7b 0d 0a 09 09 09 69 6e 74 20 79 31 20 3d 20 {.....int y1 =
0cd0: 70 73 5b 69 5d 2e 66 69 72 73 74 3b 0d 0a 09 09 ps[i].first;....
0ce0: 09 69 6e 74 20 78 31 20 3d 20 70 73 5b 69 5d 2e .int x1 = ps[i].
0cf0: 73 65 63 6f 6e 64 3b 0d 0a 09 09 09 69 6e 74 20 second;.....int
0d00: 79 32 20 3d 20 70 73 5b 6b 5d 2e 66 69 72 73 74 y2 = ps[k].first
0d10: 3b 0d 0a 09 09 09 69 6e 74 20 78 32 20 3d 20 70 ;.....int x2 = p
0d20: 73 5b 6b 5d 2e 73 65 63 6f 6e 64 3b 0d 0a 09 09 s[k].second;....
0d30: 09 62 6f 61 72 64 5b 79 31 5d 5b 78 31 5d 20 3d .board[y1][x1] =
0d40: 20 27 4e 27 3b 0d 0a 09 09 09 62 6f 61 72 64 5b 'N';.....board[
0d50: 79 32 5d 5b 78 32 5d 20 3d 20 27 4e 27 3b 0d 0a y2][x2] = 'N';..
0d60: 09 09 09 69 66 28 6f 6b 28 62 6f 61 72 64 2c 61 ...if(ok(board,a
0d70: 73 2c 72 66 29 29 0d 0a 09 09 09 09 72 65 74 75 s,rf))......retu
0d80: 72 6e 20 32 3b 0d 0a 09 09 09 69 66 28 72 66 5b rn 2;.....if(rf[
0d90: 61 73 5b 30 5d 2e 66 69 72 73 74 5d 5b 61 73 5b as[0].first][as[
0da0: 30 5d 2e 66 69 72 73 74 5d 20 3d 3d 20 28 31 3c 0].first] == (1<
0db0: 3c 30 29 29 0d 0a 09 09 09 09 62 65 73 74 20 3d <0))......best =
0dc0: 20 6d 69 6e 28 62 65 73 74 2c 20 32 2b 73 70 6c min(best, 2+spl
0dd0: 69 74 28 62 6f 61 72 64 2c 20 61 73 5b 31 5d 2c it(board, as[1],
0de0: 20 61 73 5b 32 5d 29 29 3b 0d 0a 09 09 09 69 66 as[2]));.....if
0df0: 28 72 66 5b 61 73 5b 31 5d 2e 66 69 72 73 74 5d (rf[as[1].first]
0e00: 5b 61 73 5b 31 5d 2e 66 69 72 73 74 5d 20 3d 3d [as[1].first] ==
0e10: 20 28 31 3c 3c 31 29 29 0d 0a 09 09 09 09 62 65 (1<<1))......be
0e20: 73 74 20 3d 20 6d 69 6e 28 62 65 73 74 2c 20 32 st = min(best, 2
0e30: 2b 73 70 6c 69 74 28 62 6f 61 72 64 2c 20 61 73 +split(board, as
0e40: 5b 32 5d 2c 20 61 73 5b 30 5d 29 29 3b 0d 0a 09 [2], as[0]));...
0e50: 09 09 69 66 28 72 66 5b 61 73 5b 32 5d 2e 66 69 ..if(rf[as[2].fi
0e60: 72 73 74 5d 5b 61 73 5b 32 5d 2e 66 69 72 73 74 rst][as[2].first
0e70: 5d 20 3d 3d 20 28 31 3c 3c 32 29 29 0d 0a 09 09 ] == (1<<2))....
0e80: 09 09 62 65 73 74 20 3d 20 6d 69 6e 28 62 65 73 ..best = min(bes
0e90: 74 2c 20 32 2b 73 70 6c 69 74 28 62 6f 61 72 64 t, 2+split(board
0ea0: 2c 20 61 73 5b 30 5d 2c 20 61 73 5b 31 5d 29 29 , as[0], as[1]))
0eb0: 3b 0d 0a 09 09 09 62 6f 61 72 64 5b 79 31 5d 5b ;.....board[y1][
0ec0: 78 31 5d 20 3d 20 27 2e 27 3b 0d 0a 09 09 09 62 x1] = '.';.....b
0ed0: 6f 61 72 64 5b 79 32 5d 5b 78 32 5d 20 3d 20 27 oard[y2][x2] = '
0ee0: 2e 27 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 72 65 .';....}......re
0ef0: 74 75 72 6e 20 62 65 73 74 3b 0d 0a 09 7d 0d 0a turn best;...}..
0f00: 0d 0a 09 62 6f 6f 6c 20 6f 6b 28 63 6f 6e 73 74 ...bool ok(const
0f10: 20 76 65 63 74 6f 72 3c 73 74 72 69 6e 67 3e 26 vector<string>&
0f20: 20 42 2c 20 76 65 63 74 6f 72 3c 70 61 69 72 3c B, vector<pair<
0f30: 69 6e 74 2c 69 6e 74 3e 20 3e 26 20 61 73 2c 20 int,int> >& as,
0f40: 76 65 63 74 6f 72 3c 76 65 63 74 6f 72 3c 69 6e vector<vector<in
0f50: 74 3e 20 3e 26 20 72 66 29 0d 0a 09 7b 0d 0a 09 t> >& rf)...{...
0f60: 09 69 6e 74 20 48 20 3d 20 42 2e 73 69 7a 65 28 .int H = B.size(
0f70: 29 3b 0d 0a 09 09 69 6e 74 20 57 20 3d 20 42 5b );....int W = B[
0f80: 30 5d 2e 73 69 7a 65 28 29 3b 0d 0a 09 09 72 66 0].size();....rf
0f90: 2e 61 73 73 69 67 6e 28 48 2c 20 76 65 63 74 6f .assign(H, vecto
0fa0: 72 3c 69 6e 74 3e 28 57 2c 20 30 29 29 3b 0d 0a r<int>(W, 0));..
0fb0: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0fc0: 3c 61 73 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 <as.size(); ++i)
0fd0: 20 0d 0a 09 09 7b 0d 0a 09 09 09 69 6e 74 20 61 ....{.....int a
0fe0: 79 20 3d 20 61 73 5b 69 5d 2e 66 69 72 73 74 3b y = as[i].first;
0ff0: 0d 0a 09 09 09 69 6e 74 20 61 78 20 3d 20 61 73 .....int ax = as
1000: 5b 69 5d 2e 73 65 63 6f 6e 64 3b 0d 0a 09 09 09 [i].second;.....
1010: 72 66 5b 61 79 5d 5b 61 78 5d 20 7c 3d 20 28 31 rf[ay][ax] |= (1
1020: 3c 3c 69 29 3b 0d 0a 09 09 09 71 75 65 75 65 3c <<i);.....queue<
1030: 70 61 69 72 3c 69 6e 74 2c 69 6e 74 3e 20 3e 20 pair<int,int> >
1040: 71 3b 0d 0a 09 09 09 71 2e 70 75 73 68 28 61 73 q;.....q.push(as
1050: 5b 69 5d 29 3b 0d 0a 09 09 09 77 68 69 6c 65 28 [i]);.....while(
1060: 21 71 2e 65 6d 70 74 79 28 29 29 20 7b 0d 0a 09 !q.empty()) {...
1070: 09 09 09 69 6e 74 20 79 20 3d 20 71 2e 66 72 6f ...int y = q.fro
1080: 6e 74 28 29 2e 66 69 72 73 74 3b 0d 0a 09 09 09 nt().first;.....
1090: 09 69 6e 74 20 78 20 3d 20 71 2e 66 72 6f 6e 74 .int x = q.front
10a0: 28 29 2e 73 65 63 6f 6e 64 3b 0d 0a 09 09 09 09 ().second;......
10b0: 71 2e 70 6f 70 28 29 3b 0d 0a 09 09 09 09 66 6f q.pop();......fo
10c0: 72 28 69 6e 74 20 64 3d 30 3b 20 64 3c 34 3b 20 r(int d=0; d<4;
10d0: 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 09 69 6e 74 ++d) {.......int
10e0: 20 79 79 20 3d 20 79 2b 64 79 5b 64 5d 3b 0d 0a yy = y+dy[d];..
10f0: 09 09 09 09 09 69 6e 74 20 78 78 20 3d 20 78 2b .....int xx = x+
1100: 64 78 5b 64 5d 3b 0d 0a 09 09 09 09 09 69 66 28 dx[d];.......if(
1110: 30 3c 3d 79 79 26 26 79 79 3c 48 26 26 30 3c 3d 0<=yy&&yy<H&&0<=
1120: 78 78 26 26 78 78 3c 57 26 26 42 5b 79 5d 5b 78 xx&&xx<W&&B[y][x
1130: 5d 21 3d 27 4e 27 26 26 21 28 72 66 5b 79 79 5d ]!='N'&&!(rf[yy]
1140: 5b 78 78 5d 26 28 31 3c 3c 69 29 29 29 20 7b 0d [xx]&(1<<i))) {.
1150: 0a 09 09 09 09 09 09 72 66 5b 79 79 5d 5b 78 78 .......rf[yy][xx
1160: 5d 20 7c 3d 20 31 3c 3c 69 3b 0d 0a 09 09 09 09 ] |= 1<<i;......
1170: 09 09 71 2e 70 75 73 68 28 6d 61 6b 65 5f 70 61 ..q.push(make_pa
1180: 69 72 28 79 79 2c 78 78 29 29 3b 0d 0a 09 09 09 ir(yy,xx));.....
1190: 09 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 7d ..}......}.....}
11a0: 0d 0a 09 09 7d 0d 0a 09 09 66 6f 72 28 69 6e 74 ....}....for(int
11b0: 20 69 3d 30 3b 20 69 3c 61 73 2e 73 69 7a 65 28 i=0; i<as.size(
11c0: 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 69 66 28 72 ); ++i).....if(r
11d0: 66 5b 61 73 5b 69 5d 2e 66 69 72 73 74 5d 5b 61 f[as[i].first][a
11e0: 73 5b 69 5d 2e 73 65 63 6f 6e 64 5d 20 21 3d 20 s[i].second] !=
11f0: 28 31 3c 3c 69 29 29 0d 0a 09 09 09 09 72 65 74 (1<<i))......ret
1200: 75 72 6e 20 66 61 6c 73 65 3b 0d 0a 09 09 72 65 urn false;....re
1210: 74 75 72 6e 20 74 72 75 65 3b 0d 0a 09 7d 0d 0a turn true;...}..
1220: 0d 0a 09 69 6e 74 20 73 70 6c 69 74 28 63 6f 6e ...int split(con
1230: 73 74 20 76 65 63 74 6f 72 3c 73 74 72 69 6e 67 st vector<string
1240: 3e 26 20 42 2c 20 70 61 69 72 3c 69 6e 74 2c 69 >& B, pair<int,i
1250: 6e 74 3e 20 53 2c 20 70 61 69 72 3c 69 6e 74 2c nt> S, pair<int,
1260: 69 6e 74 3e 20 44 29 0d 0a 09 7b 0d 0a 09 09 69 int> D)...{....i
1270: 6e 74 20 4f 55 54 20 3d 20 30 2c 20 49 4e 20 3d nt OUT = 0, IN =
1280: 20 31 3b 0d 0a 09 09 74 79 70 65 64 65 66 20 70 1;....typedef p
1290: 61 69 72 3c 69 6e 74 2c 20 70 61 69 72 3c 69 6e air<int, pair<in
12a0: 74 2c 69 6e 74 3e 20 3e 20 56 65 72 74 3b 0d 0a t,int> > Vert;..
12b0: 09 09 4d 61 78 46 6c 6f 77 3c 56 65 72 74 2c 20 ..MaxFlow<Vert,
12c0: 69 6e 74 3e 2a 20 6d 66 20 3d 20 6e 65 77 20 4d int>* mf = new M
12d0: 61 78 46 6c 6f 77 3c 56 65 72 74 2c 69 6e 74 3e axFlow<Vert,int>
12e0: 3b 0d 0a 09 09 69 6e 74 20 48 20 3d 20 42 2e 73 ;....int H = B.s
12f0: 69 7a 65 28 29 3b 0d 0a 09 09 69 6e 74 20 57 20 ize();....int W
1300: 3d 20 42 5b 30 5d 2e 73 69 7a 65 28 29 3b 0d 0a = B[0].size();..
1310: 09 09 66 6f 72 28 69 6e 74 20 79 3d 30 3b 20 79 ..for(int y=0; y
1320: 3c 48 3b 20 2b 2b 79 29 0d 0a 09 09 66 6f 72 28 <H; ++y)....for(
1330: 69 6e 74 20 78 3d 30 3b 20 78 3c 57 3b 20 2b 2b int x=0; x<W; ++
1340: 78 29 0d 0a 09 09 09 69 66 28 42 5b 79 5d 5b 78 x).....if(B[y][x
1350: 5d 20 21 3d 20 27 4e 27 29 20 7b 0d 0a 09 09 09 ] != 'N') {.....
1360: 09 70 61 69 72 3c 69 6e 74 2c 69 6e 74 3e 20 70 .pair<int,int> p
1370: 28 79 2c 78 29 3b 0d 0a 09 09 09 09 66 6f 72 28 (y,x);......for(
1380: 69 6e 74 20 64 3d 30 3b 20 64 3c 34 3b 20 2b 2b int d=0; d<4; ++
1390: 64 29 20 7b 0d 0a 09 09 09 09 09 69 6e 74 20 78 d) {.......int x
13a0: 78 20 3d 20 78 2b 64 78 5b 64 5d 3b 0d 0a 09 09 x = x+dx[d];....
13b0: 09 09 09 69 6e 74 20 79 79 20 3d 20 79 2b 64 79 ...int yy = y+dy
13c0: 5b 64 5d 3b 0d 0a 09 09 09 09 09 69 66 28 30 3c [d];.......if(0<
13d0: 3d 78 78 26 26 78 78 3c 57 26 26 30 3c 3d 79 79 =xx&&xx<W&&0<=yy
13e0: 26 26 79 79 3c 48 26 26 42 5b 79 79 5d 5b 78 78 &&yy<H&&B[yy][xx
13f0: 5d 21 3d 27 4e 27 29 0d 0a 09 09 09 09 09 09 6d ]!='N')........m
1400: 66 2d 3e 61 64 64 45 64 67 65 28 6d 61 6b 65 5f f->addEdge(make_
1410: 70 61 69 72 28 4f 55 54 2c 20 70 29 2c 20 6d 61 pair(OUT, p), ma
1420: 6b 65 5f 70 61 69 72 28 49 4e 2c 20 6d 61 6b 65 ke_pair(IN, make
1430: 5f 70 61 69 72 28 79 79 2c 78 78 29 29 2c 20 31 _pair(yy,xx)), 1
1440: 29 3b 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 09 69 );......}......i
1450: 66 28 70 21 3d 53 20 26 26 20 70 21 3d 44 29 0d f(p!=S && p!=D).
1460: 0a 09 09 09 09 09 6d 66 2d 3e 61 64 64 45 64 67 ......mf->addEdg
1470: 65 28 6d 61 6b 65 5f 70 61 69 72 28 49 4e 2c 20 e(make_pair(IN,
1480: 70 29 2c 20 6d 61 6b 65 5f 70 61 69 72 28 4f 55 p), make_pair(OU
1490: 54 2c 20 70 29 2c 20 31 29 3b 0d 0a 09 09 09 7d T, p), 1);.....}
14a0: 0d 0a 09 09 69 6e 74 20 6d 20 3d 20 6d 66 2d 3e ....int m = mf->
14b0: 63 61 6c 63 28 6d 61 6b 65 5f 70 61 69 72 28 4f calc(make_pair(O
14c0: 55 54 2c 53 29 2c 20 6d 61 6b 65 5f 70 61 69 72 UT,S), make_pair
14d0: 28 49 4e 2c 44 29 29 3b 0d 0a 09 09 64 65 6c 65 (IN,D));....dele
14e0: 74 65 20 6d 66 3b 0d 0a 09 09 72 65 74 75 72 6e te mf;....return
14f0: 20 6d 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f m;...}..};..../
1500: 2f 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 / BEGIN CUT HERE
1510: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d ..#include <ctim
1520: 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 e>..double start
1530: 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 _time; string ti
1540: 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e mer().. { ostrin
1550: 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c gstream os; os <
1560: 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 < " (" << int((c
1570: 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d lock()-start_tim
1580: 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 e)/CLOCKS_PER_SE
1590: 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 C*1000) << " mse
15a0: 63 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 c)"; return os.s
15b0: 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 tr(); }..templat
15c0: 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 e<typename T> os
15d0: 74 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c tream& operator<
15e0: 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 <(ostream& os, c
15f0: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 onst vector<T>&
1600: 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 v).. { os << "{
1610: 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e ";.. for(typen
1620: 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 ame vector<T>::c
1630: 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 onst_iterator it
1640: 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d =v.begin(); it!=
1650: 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a v.end(); ++it)..
1660: 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c os << '\"' <<
1670: 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 *it << '\"' <<
1680: 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f (it+1==v.end() ?
1690: 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 "" : ", "); os
16a0: 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 << " }"; return
16b0: 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 os; }..void veri
16c0: 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 69 6e fy_case(const in
16d0: 74 26 20 45 78 70 65 63 74 65 64 2c 20 63 6f 6e t& Expected, con
16e0: 73 74 20 69 6e 74 26 20 52 65 63 65 69 76 65 64 st int& Received
16f0: 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 ) {.. bool ok =
1700: 28 45 78 70 65 63 74 65 64 20 3d 3d 20 52 65 63 (Expected == Rec
1710: 65 69 76 65 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 eived);.. if(ok)
1720: 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 cerr << "PASSED
1730: 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 " << timer() <<
1740: 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 65 endl; else { ce
1750: 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c rr << "FAILED" <
1760: 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 < timer() << end
1770: 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c 74 l;.. cerr << "\t
1780: 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 o: \"" << Expect
1790: 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e ed << '\"' << en
17a0: 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 20 dl << "\tx: \""
17b0: 3c 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 27 << Received << '
17c0: 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d \"' << endl; } }
17d0: 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 4e ..#define CASE(N
17e0: 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 74 ) {cerr << "Test
17f0: 20 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c 3c Case #" << N <<
1800: 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 3b "..." << flush;
1810: 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 start_time=cloc
1820: 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 4e k();..#define EN
1830: 44 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 5f D. verify_case(_
1840: 2c 20 42 6c 6f 63 6b 33 43 68 65 63 6b 65 72 73 , Block3Checkers
1850: 28 29 2e 62 6c 6f 63 6b 54 68 65 6d 28 62 6f 61 ().blockThem(boa
1860: 72 64 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e rd));}..int main
1870: 28 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d 0a (){....CASE(0)..
1880: 09 73 74 72 69 6e 67 20 62 6f 61 72 64 5f 5b 5d .string board_[]
1890: 20 3d 20 7b 22 41 2e 2e 2e 2e 2e 2e 41 22 2c 0d = {"A......A",.
18a0: 0a 20 22 2e 2e 2e 4e 2e 4e 2e 2e 22 2c 0d 0a 20 . "...N.N..",..
18b0: 22 2e 4e 4e 4e 2e 4e 4e 2e 22 2c 0d 0a 20 22 4e ".NNN.NN.",.. "N
18c0: 4e 4e 4e 2e 4e 2e 4e 22 2c 0d 0a 20 22 4e 2e 4e NNN.N.N",.. "N.N
18d0: 4e 2e 4e 4e 4e 22 2c 0d 0a 20 22 2e 4e 4e 4e 2e N.NNN",.. ".NNN.
18e0: 4e 4e 4e 22 2c 0d 0a 20 22 4e 4e 4e 2e 2e 2e 4e NNN",.. "NNN...N
18f0: 4e 22 2c 0d 0a 20 22 2e 4e 4e 2e 41 2e 2e 4e 22 N",.. ".NN.A..N"
1900: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 };... vector <s
1910: 74 72 69 6e 67 3e 20 62 6f 61 72 64 28 62 6f 61 tring> board(boa
1920: 72 64 5f 2c 20 62 6f 61 72 64 5f 2b 73 69 7a 65 rd_, board_+size
1930: 6f 66 28 62 6f 61 72 64 5f 29 2f 73 69 7a 65 6f of(board_)/sizeo
1940: 66 28 2a 62 6f 61 72 64 5f 29 29 3b 20 0d 0a 09 f(*board_)); ...
1950: 69 6e 74 20 5f 20 3d 20 31 3b 20 0d 0a 45 4e 44 int _ = 1; ..END
1960: 0d 0a 43 41 53 45 28 31 29 0d 0a 09 73 74 72 69 ..CASE(1)...stri
1970: 6e 67 20 62 6f 61 72 64 5f 5b 5d 20 3d 20 7b 22 ng board_[] = {"
1980: 2e 2e 2e 2e 2e 41 22 2c 0d 0a 20 22 2e 2e 2e 2e .....A",.. "....
1990: 2e 2e 22 2c 0d 0a 20 22 2e 2e 2e 2e 2e 2e 22 2c ..",.. "......",
19a0: 0d 0a 20 22 4e 4e 4e 4e 4e 4e 22 2c 0d 0a 20 22 .. "NNNNNN",.. "
19b0: 41 2e 2e 2e 2e 2e 22 2c 0d 0a 20 22 41 2e 2e 2e A.....",.. "A...
19c0: 2e 2e 22 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 .."};... vector
19d0: 20 3c 73 74 72 69 6e 67 3e 20 62 6f 61 72 64 28 <string> board(
19e0: 62 6f 61 72 64 5f 2c 20 62 6f 61 72 64 5f 2b 73 board_, board_+s
19f0: 69 7a 65 6f 66 28 62 6f 61 72 64 5f 29 2f 73 69 izeof(board_)/si
1a00: 7a 65 6f 66 28 2a 62 6f 61 72 64 5f 29 29 3b 20 zeof(*board_));
1a10: 0d 0a 09 69 6e 74 20 5f 20 3d 20 31 30 30 3b 20 ...int _ = 100;
1a20: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a ..END..CASE(2)..
1a30: 09 73 74 72 69 6e 67 20 62 6f 61 72 64 5f 5b 5d .string board_[]
1a40: 20 3d 20 7b 22 41 2e 4e 22 2c 0d 0a 20 22 4e 4e = {"A.N",.. "NN
1a50: 41 22 2c 0d 0a 20 22 41 4e 2e 22 7d 3b 0d 0a 09 A",.. "AN."};...
1a60: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
1a70: 3e 20 62 6f 61 72 64 28 62 6f 61 72 64 5f 2c 20 > board(board_,
1a80: 62 6f 61 72 64 5f 2b 73 69 7a 65 6f 66 28 62 6f board_+sizeof(bo
1a90: 61 72 64 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 6f ard_)/sizeof(*bo
1aa0: 61 72 64 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f ard_)); ...int _
1ab0: 20 3d 20 30 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 = 0; ..END..CAS
1ac0: 45 28 33 29 0d 0a 09 73 74 72 69 6e 67 20 62 6f E(3)...string bo
1ad0: 61 72 64 5f 5b 5d 20 3d 20 7b 22 2e 2e 2e 2e 2e ard_[] = {".....
1ae0: 2e 4e 41 22 2c 0d 0a 20 22 2e 4e 4e 4e 4e 2e 4e .NA",.. ".NNNN.N
1af0: 2e 22 2c 0d 0a 20 22 2e 4e 2e 2e 2e 2e 2e 2e 22 .",.. ".N......"
1b00: 2c 0d 0a 20 22 2e 2e 2e 2e 4e 4e 4e 4e 22 2c 0d ,.. "....NNNN",.
1b10: 0a 20 22 2e 2e 2e 2e 2e 2e 2e 2e 22 2c 0d 0a 20 . "........",..
1b20: 22 2e 4e 2e 2e 4e 4e 4e 2e 22 2c 0d 0a 20 22 2e ".N..NNN.",.. ".
1b30: 2e 2e 2e 2e 2e 4e 2e 22 2c 0d 0a 20 22 41 2e 4e .....N.",.. "A.N
1b40: 2e 2e 2e 2e 41 22 7d 0d 0a 3b 0d 0a 09 20 20 76 ....A"}..;... v
1b50: 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 62 ector <string> b
1b60: 6f 61 72 64 28 62 6f 61 72 64 5f 2c 20 62 6f 61 oard(board_, boa
1b70: 72 64 5f 2b 73 69 7a 65 6f 66 28 62 6f 61 72 64 rd_+sizeof(board
1b80: 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 6f 61 72 64 _)/sizeof(*board
1b90: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 _)); ...int _ =
1ba0: 33 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d 0a 43 41 3; ..END../*..CA
1bb0: 53 45 28 34 29 0d 0a 09 73 74 72 69 6e 67 20 62 SE(4)...string b
1bc0: 6f 61 72 64 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 oard_[] = ;...
1bd0: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
1be0: 62 6f 61 72 64 28 62 6f 61 72 64 5f 2c 20 62 6f board(board_, bo
1bf0: 61 72 64 5f 2b 73 69 7a 65 6f 66 28 62 6f 61 72 ard_+sizeof(boar
1c00: 64 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 6f 61 72 d_)/sizeof(*boar
1c10: 64 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d d_)); ...int _ =
1c20: 20 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 ; ..END..CASE(5
1c30: 29 0d 0a 09 73 74 72 69 6e 67 20 62 6f 61 72 64 )...string board
1c40: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
1c50: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 62 6f 61 72 or <string> boar
1c60: 64 28 62 6f 61 72 64 5f 2c 20 62 6f 61 72 64 5f d(board_, board_
1c70: 2b 73 69 7a 65 6f 66 28 62 6f 61 72 64 5f 29 2f +sizeof(board_)/
1c80: 73 69 7a 65 6f 66 28 2a 62 6f 61 72 64 5f 29 29 sizeof(*board_))
1c90: 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 3b 20 0d ; ...int _ = ; .
1ca0: 0a 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 .END..*/..}..//
1cb0: 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a END CUT HERE..