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 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 63 73 74 72 69 6e 67 3e 0d 0a 75 73 69 6e 67 <cstring>..using
0150: 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d namespace std;.
0160: 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f .typedef long lo
0170: 6e 67 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 ng LL;..typedef
0180: 63 6f 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 complex<double>
0190: 43 4d 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 49 6e CMP;....class In
01a0: 66 69 6e 69 74 65 4c 61 62 20 7b 20 70 75 62 6c finiteLab { publ
01b0: 69 63 3a 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 ic:...long long
01c0: 67 65 74 44 69 73 74 61 6e 63 65 28 76 65 63 74 getDistance(vect
01d0: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 6d 61 70 2c or <string> map,
01e0: 20 6c 6f 6e 67 20 6c 6f 6e 67 20 72 31 2c 20 69 long long r1, i
01f0: 6e 74 20 63 31 2c 20 6c 6f 6e 67 20 6c 6f 6e 67 nt c1, long long
0200: 20 72 32 2c 20 69 6e 74 20 63 32 29 20 0d 0a 09 r2, int c2) ...
0210: 7b 0d 0a 09 09 4c 4c 20 48 20 3d 20 6d 61 70 2e {....LL H = map.
0220: 73 69 7a 65 28 29 3b 0d 0a 09 09 4c 4c 20 57 20 size();....LL W
0230: 3d 20 6d 61 70 5b 30 5d 2e 73 69 7a 65 28 29 3b = map[0].size();
0240: 0d 0a 0d 0a 09 09 69 66 28 20 72 31 20 3e 20 72 ......if( r1 > r
0250: 32 20 29 20 7b 0d 0a 09 09 09 73 77 61 70 28 72 2 ) {.....swap(r
0260: 31 2c 72 32 29 3b 0d 0a 09 09 09 73 77 61 70 28 1,r2);.....swap(
0270: 63 31 2c 63 32 29 3b 0d 0a 09 09 7d 0d 0a 09 09 c1,c2);....}....
0280: 69 66 28 20 72 31 20 3c 20 30 20 29 20 7b 0d 0a if( r1 < 0 ) {..
0290: 09 09 09 2f 2f 20 63 68 65 63 6b 21 21 21 21 0d ...// check!!!!.
02a0: 0a 09 09 09 4c 4c 20 48 78 20 3d 20 28 2d 72 31 ....LL Hx = (-r1
02b0: 2f 48 20 2b 20 31 29 2a 48 3b 0d 0a 09 09 09 72 /H + 1)*H;.....r
02c0: 31 20 2b 3d 20 48 78 3b 0d 0a 09 09 09 72 32 20 1 += Hx;.....r2
02d0: 2b 3d 20 48 78 3b 0d 0a 09 09 7d 0d 0a 09 09 63 += Hx;....}....c
02e0: 65 72 72 20 3c 3c 20 72 31 20 3c 3c 20 22 20 22 err << r1 << " "
02f0: 20 3c 3c 20 72 32 20 3c 3c 20 65 6e 64 6c 3b 0d << r2 << endl;.
0300: 0a 0d 0a 09 09 76 65 63 74 6f 72 3c 73 74 72 69 .....vector<stri
0310: 6e 67 3e 20 6d 6d 6d 28 6d 61 70 29 3b 0d 0a 09 ng> mmm(map);...
0320: 09 6d 6d 6d 2e 69 6e 73 65 72 74 28 6d 6d 6d 2e .mmm.insert(mmm.
0330: 65 6e 64 28 29 2c 20 6d 61 70 2e 62 65 67 69 6e end(), map.begin
0340: 28 29 2c 20 6d 61 70 2e 65 6e 64 28 29 29 3b 0d (), map.end());.
0350: 0a 09 09 6d 6d 6d 2e 69 6e 73 65 72 74 28 6d 6d ...mmm.insert(mm
0360: 6d 2e 65 6e 64 28 29 2c 20 6d 61 70 2e 62 65 67 m.end(), map.beg
0370: 69 6e 28 29 2c 20 6d 61 70 2e 65 6e 64 28 29 29 in(), map.end())
0380: 3b 0d 0a 0d 0a 09 09 69 66 28 20 72 31 2f 48 20 ;......if( r1/H
0390: 3d 3d 20 72 32 2f 48 20 29 0d 0a 09 09 09 72 65 == r2/H ).....re
03a0: 74 75 72 6e 20 64 69 73 74 28 6d 6d 6d 2c 20 48 turn dist(mmm, H
03b0: 2b 28 72 31 25 48 29 2c 20 63 31 2c 20 48 2b 28 +(r1%H), c1, H+(
03c0: 72 32 25 48 29 2c 20 63 32 29 3b 0d 0a 09 09 72 r2%H), c2);....r
03d0: 65 74 75 72 6e 20 2d 31 3b 0d 0a 0d 0a 09 09 2f eturn -1;....../
03e0: 2f 20 74 6f 70 20 74 6f 20 74 6f 70 0d 0a 09 09 / top to top....
03f0: 76 65 63 74 6f 72 3c 76 65 63 74 6f 72 3c 4c 4c vector<vector<LL
0400: 3e 20 3e 20 74 6f 63 68 75 28 57 2c 20 76 65 63 > > tochu(W, vec
0410: 74 6f 72 3c 4c 4c 3e 28 57 2c 20 2d 31 29 29 3b tor<LL>(W, -1));
0420: 0d 0a 09 09 66 6f 72 28 69 6e 74 20 78 31 3d 30 ....for(int x1=0
0430: 3b 20 78 31 3c 57 3b 20 2b 2b 78 31 29 20 69 66 ; x1<W; ++x1) if
0440: 28 20 6d 61 70 5b 30 5d 5b 78 31 5d 20 21 3d 20 ( map[0][x1] !=
0450: 27 23 27 20 29 0d 0a 09 09 66 6f 72 28 69 6e 74 '#' )....for(int
0460: 20 78 32 3d 30 3b 20 78 32 3c 57 3b 20 2b 2b 78 x2=0; x2<W; ++x
0470: 32 29 20 69 66 28 20 6d 61 70 5b 30 5d 5b 78 32 2) if( map[0][x2
0480: 5d 20 21 3d 20 27 23 27 20 29 0d 0a 09 09 09 74 ] != '#' ).....t
0490: 6f 63 68 75 5b 78 31 5d 5b 78 32 5d 20 3d 20 64 ochu[x1][x2] = d
04a0: 69 73 74 28 20 6d 6d 6d 2c 20 48 2c 20 78 31 2c ist( mmm, H, x1,
04b0: 20 48 2a 32 2c 20 78 32 20 29 3b 0d 0a 0d 0a 09 H*2, x2 );.....
04c0: 09 2f 2f 20 72 31 63 31 20 74 6f 20 74 6f 70 0d .// r1c1 to top.
04d0: 0a 09 09 76 65 63 74 6f 72 3c 4c 4c 3e 20 66 72 ...vector<LL> fr
04e0: 6f 6d 28 57 2c 20 2d 31 29 3b 0d 0a 09 09 66 6f om(W, -1);....fo
04f0: 72 28 69 6e 74 20 78 31 3d 30 3b 20 78 31 3c 57 r(int x1=0; x1<W
0500: 3b 20 2b 2b 78 31 29 20 69 66 28 20 6d 61 70 5b ; ++x1) if( map[
0510: 30 5d 5b 78 31 5d 20 21 3d 20 27 23 27 20 29 0d 0][x1] != '#' ).
0520: 0a 09 09 09 66 72 6f 6d 5b 57 5d 20 3d 20 64 69 ....from[W] = di
0530: 73 74 28 20 6d 6d 6d 2c 20 48 2b 28 72 31 25 48 st( mmm, H+(r1%H
0540: 29 2c 20 63 31 2c 20 48 2a 32 2c 20 78 31 20 29 ), c1, H*2, x1 )
0550: 3b 0d 0a 0d 0a 09 09 2f 2f 20 74 6f 70 20 74 6f ;......// top to
0560: 20 72 32 63 32 0d 0a 09 09 76 65 63 74 6f 72 3c r2c2....vector<
0570: 4c 4c 3e 20 74 6f 28 57 2c 20 2d 31 29 3b 0d 0a LL> to(W, -1);..
0580: 09 09 66 6f 72 28 69 6e 74 20 78 31 3d 30 3b 20 ..for(int x1=0;
0590: 78 31 3c 57 3b 20 2b 2b 78 31 29 20 69 66 28 20 x1<W; ++x1) if(
05a0: 6d 61 70 5b 30 5d 5b 78 31 5d 20 21 3d 20 27 23 map[0][x1] != '#
05b0: 27 20 29 0d 0a 09 09 09 74 6f 5b 57 5d 20 3d 20 ' ).....to[W] =
05c0: 64 69 73 74 28 20 6d 6d 6d 2c 20 48 2c 20 78 31 dist( mmm, H, x1
05d0: 2c 20 48 2a 32 2b 28 72 32 25 48 29 2c 20 63 32 , H*2+(r2%H), c2
05e0: 20 29 3b 0d 0a 0d 0a 09 09 4c 4c 20 62 65 73 74 );......LL best
05f0: 20 3d 20 2d 31 3b 0d 0a 09 09 66 6f 72 28 69 6e = -1;....for(in
0600: 74 20 69 3d 30 3b 20 69 3c 66 72 6f 6d 2e 73 69 t i=0; i<from.si
0610: 7a 65 28 29 3b 20 2b 2b 69 29 20 69 66 28 20 66 ze(); ++i) if( f
0620: 72 6f 6d 5b 69 5d 3e 3d 30 20 29 0d 0a 09 09 09 rom[i]>=0 ).....
0630: 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 74 for(int j=0; j<t
0640: 6f 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 20 69 o.size(); ++j) i
0650: 66 28 20 74 6f 5b 6a 5d 3e 3d 30 20 29 0d 0a 09 f( to[j]>=0 )...
0660: 09 09 7b 0d 0a 09 09 09 09 4c 4c 20 73 63 20 3d ..{......LL sc =
0670: 20 66 72 6f 6d 5b 69 5d 20 2b 20 74 6f 5b 6a 5d from[i] + to[j]
0680: 3b 0d 0a 09 09 09 09 4c 4c 20 73 32 20 3d 20 2d ;......LL s2 = -
0690: 31 3b 20 2f 2f 20 54 4f 44 4f 21 0d 0a 09 09 09 1; // TODO!.....
06a0: 09 69 66 28 20 73 32 20 21 3d 20 2d 31 20 26 26 .if( s2 != -1 &&
06b0: 20 28 62 65 73 74 20 3d 3d 20 2d 31 20 7c 7c 20 (best == -1 ||
06c0: 73 32 2b 73 63 3c 62 65 73 74 29 20 29 0d 0a 09 s2+sc<best) )...
06d0: 09 09 09 09 62 65 73 74 20 3d 20 73 32 2b 73 63 ....best = s2+sc
06e0: 3b 0d 0a 09 09 09 7d 0d 0a 09 09 72 65 74 75 72 ;.....}....retur
06f0: 6e 20 62 65 73 74 3b 0d 0a 09 7d 0d 0a 0d 0a 09 n best;...}.....
0700: 4c 4c 20 64 69 73 74 28 76 65 63 74 6f 72 3c 73 LL dist(vector<s
0710: 74 72 69 6e 67 3e 26 20 6d 6d 6d 2c 20 4c 4c 20 tring>& mmm, LL
0720: 79 31 2c 20 4c 4c 20 78 31 2c 20 4c 4c 20 79 32 y1, LL x1, LL y2
0730: 2c 20 4c 4c 20 78 32 29 0d 0a 09 7b 0d 0a 09 09 , LL x2)...{....
0740: 76 65 63 74 6f 72 3c 20 70 61 69 72 3c 4c 4c 2c vector< pair<LL,
0750: 4c 4c 3e 20 3e 20 51 3b 0d 0a 09 09 73 65 74 3c LL> > Q;....set<
0760: 20 70 61 69 72 3c 4c 4c 2c 4c 4c 3e 20 3e 20 56 pair<LL,LL> > V
0770: 3b 0d 0a 09 09 51 2e 70 75 73 68 5f 62 61 63 6b ;....Q.push_back
0780: 28 20 6d 61 6b 65 5f 70 61 69 72 28 79 31 2c 78 ( make_pair(y1,x
0790: 31 29 20 29 3b 0d 0a 09 09 56 2e 69 6e 73 65 72 1) );....V.inser
07a0: 74 28 20 6d 61 6b 65 5f 70 61 69 72 28 79 31 2c t( make_pair(y1,
07b0: 78 31 29 20 29 3b 0d 0a 09 09 66 6f 72 28 69 6e x1) );....for(in
07c0: 74 20 64 3d 30 3b 20 21 51 2e 65 6d 70 74 79 28 t d=0; !Q.empty(
07d0: 29 3b 20 2b 2b 64 29 0d 0a 09 09 7b 0d 0a 09 09 ); ++d)....{....
07e0: 09 76 65 63 74 6f 72 3c 20 70 61 69 72 3c 4c 4c .vector< pair<LL
07f0: 2c 4c 4c 3e 20 3e 20 51 5f 6e 65 78 74 3b 0d 0a ,LL> > Q_next;..
0800: 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0810: 69 3c 51 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 i<Q.size(); ++i)
0820: 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 4c 4c 20 79 .....{......LL y
0830: 20 3d 20 51 5b 69 5d 2e 66 69 72 73 74 3b 0d 0a = Q[i].first;..
0840: 09 09 09 09 4c 4c 20 78 20 3d 20 51 5b 69 5d 2e ....LL x = Q[i].
0850: 73 65 63 6f 6e 64 3b 0d 0a 09 09 09 09 69 66 28 second;......if(
0860: 20 79 3d 3d 79 32 20 26 26 20 78 3d 3d 78 32 20 y==y2 && x==x2
0870: 29 0d 0a 09 09 09 09 09 72 65 74 75 72 6e 20 64 ).......return d
0880: 3b 0d 0a 09 09 09 09 69 6e 74 20 64 79 5b 5d 20 ;......int dy[]
0890: 3d 20 7b 2d 31 2c 2b 31 2c 30 2c 30 7d 3b 0d 0a = {-1,+1,0,0};..
08a0: 09 09 09 09 69 6e 74 20 64 78 5b 5d 20 3d 20 7b ....int dx[] = {
08b0: 30 2c 30 2c 2d 31 2c 2b 31 7d 3b 0d 0a 09 09 09 0,0,-1,+1};.....
08c0: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
08d0: 34 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 09 09 4; ++i) {.......
08e0: 4c 4c 20 79 79 20 3d 20 79 2b 64 79 5b 69 5d 3b LL yy = y+dy[i];
08f0: 0d 0a 09 09 09 09 09 4c 4c 20 78 78 20 3d 20 78 .......LL xx = x
0900: 2b 64 78 5b 69 5d 3b 0d 0a 09 09 09 09 09 69 66 +dx[i];.......if
0910: 28 20 30 3c 3d 79 79 20 26 26 20 79 79 3c 6d 6d ( 0<=yy && yy<mm
0920: 6d 2e 73 69 7a 65 28 29 20 26 26 20 30 3c 3d 78 m.size() && 0<=x
0930: 78 20 26 26 20 78 78 3c 6d 6d 6d 5b 30 5d 2e 73 x && xx<mmm[0].s
0940: 69 7a 65 28 29 20 26 26 20 6d 6d 6d 5b 79 79 5d ize() && mmm[yy]
0950: 5b 78 78 5d 21 3d 27 23 27 20 29 20 7b 0d 0a 09 [xx]!='#' ) {...
0960: 09 09 09 09 09 70 61 69 72 3c 4c 4c 2c 4c 4c 3e .....pair<LL,LL>
0970: 20 70 28 79 79 2c 78 78 29 3b 0d 0a 09 09 09 09 p(yy,xx);......
0980: 09 09 69 66 28 20 21 20 56 2e 63 6f 75 6e 74 28 ..if( ! V.count(
0990: 70 29 20 29 20 7b 0d 0a 09 09 09 09 09 09 09 56 p) ) {.........V
09a0: 2e 69 6e 73 65 72 74 28 70 29 3b 0d 0a 09 09 09 .insert(p);.....
09b0: 09 09 09 09 51 5f 6e 65 78 74 2e 70 75 73 68 5f ....Q_next.push_
09c0: 62 61 63 6b 28 70 29 3b 0d 0a 09 09 09 09 09 09 back(p);........
09d0: 7d 0d 0a 09 09 09 09 09 7d 0d 0a 09 09 09 09 7d }.......}......}
09e0: 0d 0a 09 09 09 09 69 66 28 20 6d 6d 6d 5b 79 5d ......if( mmm[y]
09f0: 5b 78 5d 20 3d 3d 20 27 54 27 20 29 20 7b 0d 0a [x] == 'T' ) {..
0a00: 09 09 09 09 09 66 6f 72 28 69 6e 74 20 78 74 3d .....for(int xt=
0a10: 30 3b 20 78 74 3c 6d 6d 6d 5b 79 5d 2e 73 69 7a 0; xt<mmm[y].siz
0a20: 65 28 29 3b 20 2b 2b 78 74 29 20 69 66 28 78 74 e(); ++xt) if(xt
0a30: 21 3d 78 20 26 26 20 6d 6d 6d 5b 79 5d 5b 78 74 !=x && mmm[y][xt
0a40: 5d 3d 3d 27 54 27 29 20 7b 0d 0a 09 09 09 09 09 ]=='T') {.......
0a50: 09 70 61 69 72 3c 4c 4c 2c 4c 4c 3e 20 70 28 79 .pair<LL,LL> p(y
0a60: 2c 78 74 29 3b 0d 0a 09 09 09 09 09 09 69 66 28 ,xt);........if(
0a70: 20 21 20 56 2e 63 6f 75 6e 74 28 70 29 20 29 20 ! V.count(p) )
0a80: 7b 0d 0a 09 09 09 09 09 09 09 56 2e 69 6e 73 65 {.........V.inse
0a90: 72 74 28 70 29 3b 0d 0a 09 09 09 09 09 09 09 51 rt(p);.........Q
0aa0: 5f 6e 65 78 74 2e 70 75 73 68 5f 62 61 63 6b 28 _next.push_back(
0ab0: 70 29 3b 0d 0a 09 09 09 09 09 09 7d 0d 0a 09 09 p);........}....
0ac0: 09 09 09 09 62 72 65 61 6b 3b 0d 0a 09 09 09 09 ....break;......
0ad0: 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 7d 0d .}......}.....}.
0ae0: 0a 09 09 09 51 5f 6e 65 78 74 2e 73 77 61 70 28 ....Q_next.swap(
0af0: 51 29 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 74 75 Q);....}....retu
0b00: 72 6e 20 2d 31 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a rn -1;...}..};..
0b10: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
0b20: 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 ERE..#include <c
0b30: 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 time>..double st
0b40: 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 art_time; string
0b50: 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 timer().. { ost
0b60: 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f ringstream os; o
0b70: 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 s << " (" << int
0b80: 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f ((clock()-start_
0b90: 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 time)/CLOCKS_PER
0ba0: 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 _SEC*1000) << "
0bb0: 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f msec)"; return o
0bc0: 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 s.str(); }..temp
0bd0: 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e late<typename T>
0be0: 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 ostream& operat
0bf0: 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 or<<(ostream& os
0c00: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 , const vector<T
0c10: 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 >& v).. { os <<
0c20: 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 "{ ";.. for(ty
0c30: 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e pename vector<T>
0c40: 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 ::const_iterator
0c50: 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 it=v.begin(); i
0c60: 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 t!=v.end(); ++it
0c70: 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 ).. os << '\"'
0c80: 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 << *it << '\"'
0c90: 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 << (it+1==v.end(
0ca0: 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 ) ? "" : ", ");
0cb0: 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 os << " }"; retu
0cc0: 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 rn os; }..void v
0cd0: 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 erify_case(const
0ce0: 20 6c 6f 6e 67 20 6c 6f 6e 67 26 20 45 78 70 65 long long& Expe
0cf0: 63 74 65 64 2c 20 63 6f 6e 73 74 20 6c 6f 6e 67 cted, const long
0d00: 20 6c 6f 6e 67 26 20 52 65 63 65 69 76 65 64 29 long& Received)
0d10: 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 {.. bool ok = (
0d20: 45 78 70 65 63 74 65 64 20 3d 3d 20 52 65 63 65 Expected == Rece
0d30: 69 76 65 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 ived);.. if(ok)
0d40: 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 22 cerr << "PASSED"
0d50: 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 << timer() << e
0d60: 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 ndl; else { cer
0d70: 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c r << "FAILED" <<
0d80: 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c timer() << endl
0d90: 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f ;.. cerr << "\to
0da0: 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 : \"" << Expecte
0db0: 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 d << '\"' << end
0dc0: 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c l << "\tx: \"" <
0dd0: 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 27 5c < Received << '\
0de0: 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d "' << endl; } }.
0df0: 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 4e 29 .#define CASE(N)
0e00: 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 {cerr << "Test
0e10: 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 Case #" << N <<
0e20: 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 "..." << flush;
0e30: 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b start_time=clock
0e40: 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 ();..#define END
0e50: 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 5f 2c . verify_case(_,
0e60: 20 49 6e 66 69 6e 69 74 65 4c 61 62 28 29 2e 67 InfiniteLab().g
0e70: 65 74 44 69 73 74 61 6e 63 65 28 6d 61 70 2c 20 etDistance(map,
0e80: 72 31 2c 20 63 31 2c 20 72 32 2c 20 63 32 29 29 r1, c1, r2, c2))
0e90: 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d ;}..int main(){.
0ea0: 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 73 74 72 ...CASE(0)...str
0eb0: 69 6e 67 20 6d 61 70 5f 5b 5d 20 3d 20 7b 22 23 ing map_[] = {"#
0ec0: 2e 2e 2e 23 23 22 2c 0d 0a 20 22 2e 23 23 2e 2e ...##",.. ".##..
0ed0: 2e 22 2c 0d 0a 20 22 2e 2e 23 2e 23 23 22 2c 0d .",.. "..#.##",.
0ee0: 0a 20 22 23 2e 23 2e 23 23 22 7d 3b 0d 0a 09 20 . "#.#.##"};...
0ef0: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
0f00: 20 6d 61 70 28 6d 61 70 5f 2c 20 6d 61 70 5f 2b map(map_, map_+
0f10: 73 69 7a 65 6f 66 28 6d 61 70 5f 29 2f 73 69 7a sizeof(map_)/siz
0f20: 65 6f 66 28 2a 6d 61 70 5f 29 29 3b 20 0d 0a 09 eof(*map_)); ...
0f30: 6c 6f 6e 67 20 6c 6f 6e 67 20 72 31 20 3d 20 31 long long r1 = 1
0f40: 4c 4c 3b 20 0d 0a 09 69 6e 74 20 63 31 20 3d 20 LL; ...int c1 =
0f50: 30 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 0; ...long long
0f60: 72 32 20 3d 20 35 4c 4c 3b 20 0d 0a 09 69 6e 74 r2 = 5LL; ...int
0f70: 20 63 32 20 3d 20 33 3b 20 0d 0a 09 6c 6f 6e 67 c2 = 3; ...long
0f80: 20 6c 6f 6e 67 20 5f 20 3d 20 37 4c 4c 3b 20 0d long _ = 7LL; .
0f90: 0a 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 .END..CASE(1)...
0fa0: 73 74 72 69 6e 67 20 6d 61 70 5f 5b 5d 20 3d 20 string map_[] =
0fb0: 7b 22 23 23 2e 23 2e 22 2c 0d 0a 20 22 2e 23 54 {"##.#.",.. ".#T
0fc0: 23 54 22 2c 0d 0a 20 22 2e 2e 2e 23 2e 22 2c 0d #T",.. "...#.",.
0fd0: 0a 20 22 23 23 2e 23 2e 22 7d 3b 0d 0a 09 20 20 . "##.#."};...
0fe0: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
0ff0: 6d 61 70 28 6d 61 70 5f 2c 20 6d 61 70 5f 2b 73 map(map_, map_+s
1000: 69 7a 65 6f 66 28 6d 61 70 5f 29 2f 73 69 7a 65 izeof(map_)/size
1010: 6f 66 28 2a 6d 61 70 5f 29 29 3b 20 0d 0a 09 6c of(*map_)); ...l
1020: 6f 6e 67 20 6c 6f 6e 67 20 72 31 20 3d 20 37 4c ong long r1 = 7L
1030: 4c 3b 20 0d 0a 09 69 6e 74 20 63 31 20 3d 20 34 L; ...int c1 = 4
1040: 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 72 ; ...long long r
1050: 32 20 3d 20 31 4c 4c 3b 20 0d 0a 09 69 6e 74 20 2 = 1LL; ...int
1060: 63 32 20 3d 20 30 3b 20 0d 0a 09 6c 6f 6e 67 20 c2 = 0; ...long
1070: 6c 6f 6e 67 20 5f 20 3d 20 39 4c 4c 3b 20 0d 0a long _ = 9LL; ..
1080: 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 73 END..CASE(2)...s
1090: 74 72 69 6e 67 20 6d 61 70 5f 5b 5d 20 3d 20 7b tring map_[] = {
10a0: 22 2e 2e 23 23 23 23 23 23 2e 23 22 2c 0d 0a 20 "..######.#",..
10b0: 22 2e 23 23 23 54 23 23 23 2e 54 22 2c 0d 0a 20 ".###T###.T",..
10c0: 22 2e 2e 54 23 2e 23 23 54 23 23 22 2c 0d 0a 20 "..T#.##T##",..
10d0: 22 2e 23 23 23 23 23 23 2e 2e 23 22 7d 3b 0d 0a ".######..#"};..
10e0: 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e . vector <strin
10f0: 67 3e 20 6d 61 70 28 6d 61 70 5f 2c 20 6d 61 70 g> map(map_, map
1100: 5f 2b 73 69 7a 65 6f 66 28 6d 61 70 5f 29 2f 73 _+sizeof(map_)/s
1110: 69 7a 65 6f 66 28 2a 6d 61 70 5f 29 29 3b 20 0d izeof(*map_)); .
1120: 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 72 31 20 3d ..long long r1 =
1130: 20 31 4c 4c 3b 20 0d 0a 09 69 6e 74 20 63 31 20 1LL; ...int c1
1140: 3d 20 30 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e = 0; ...long lon
1150: 67 20 72 32 20 3d 20 36 4c 4c 3b 20 0d 0a 09 69 g r2 = 6LL; ...i
1160: 6e 74 20 63 32 20 3d 20 34 3b 20 0d 0a 09 6c 6f nt c2 = 4; ...lo
1170: 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 31 4c 4c ng long _ = 11LL
1180: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 ; ..END..CASE(3)
1190: 0d 0a 09 73 74 72 69 6e 67 20 6d 61 70 5f 5b 5d ...string map_[]
11a0: 20 3d 20 7b 22 2e 2e 23 2e 2e 22 2c 0d 0a 20 22 = {"..#..",.. "
11b0: 2e 23 2e 23 2e 22 2c 0d 0a 20 22 2e 2e 2e 2e 2e .#.#.",.. ".....
11c0: 22 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c "};... vector <
11d0: 73 74 72 69 6e 67 3e 20 6d 61 70 28 6d 61 70 5f string> map(map_
11e0: 2c 20 6d 61 70 5f 2b 73 69 7a 65 6f 66 28 6d 61 , map_+sizeof(ma
11f0: 70 5f 29 2f 73 69 7a 65 6f 66 28 2a 6d 61 70 5f p_)/sizeof(*map_
1200: 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 )); ...long long
1210: 20 72 31 20 3d 20 2d 32 39 4c 4c 3b 20 0d 0a 09 r1 = -29LL; ...
1220: 69 6e 74 20 63 31 20 3d 20 32 3b 20 0d 0a 09 6c int c1 = 2; ...l
1230: 6f 6e 67 20 6c 6f 6e 67 20 72 32 20 3d 20 31 39 ong long r2 = 19
1240: 4c 4c 3b 20 0d 0a 09 69 6e 74 20 63 32 20 3d 20 LL; ...int c2 =
1250: 32 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 2; ...long long
1260: 5f 20 3d 20 35 34 4c 4c 3b 20 0d 0a 45 4e 44 0d _ = 54LL; ..END.
1270: 0a 43 41 53 45 28 34 29 0d 0a 09 73 74 72 69 6e .CASE(4)...strin
1280: 67 20 6d 61 70 5f 5b 5d 20 3d 20 7b 22 2e 23 2e g map_[] = {".#.
1290: 23 2e 22 2c 0d 0a 20 22 2e 2e 23 2e 2e 22 2c 0d #.",.. "..#..",.
12a0: 0a 20 22 2e 2e 2e 2e 2e 22 2c 0d 0a 20 22 2e 2e . ".....",.. "..
12b0: 2e 2e 2e 22 2c 0d 0a 20 22 2e 2e 23 2e 2e 22 7d ...",.. "..#.."}
12c0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 ;... vector <st
12d0: 72 69 6e 67 3e 20 6d 61 70 28 6d 61 70 5f 2c 20 ring> map(map_,
12e0: 6d 61 70 5f 2b 73 69 7a 65 6f 66 28 6d 61 70 5f map_+sizeof(map_
12f0: 29 2f 73 69 7a 65 6f 66 28 2a 6d 61 70 5f 29 29 )/sizeof(*map_))
1300: 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 72 ; ...long long r
1310: 31 20 3d 20 2d 39 39 39 4c 4c 3b 20 0d 0a 09 69 1 = -999LL; ...i
1320: 6e 74 20 63 31 20 3d 20 33 3b 20 0d 0a 09 6c 6f nt c1 = 3; ...lo
1330: 6e 67 20 6c 6f 6e 67 20 72 32 20 3d 20 31 30 30 ng long r2 = 100
1340: 4c 4c 3b 20 0d 0a 09 69 6e 74 20 63 32 20 3d 20 LL; ...int c2 =
1350: 32 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 2; ...long long
1360: 5f 20 3d 20 2d 31 4c 4c 3b 20 0d 0a 45 4e 44 0d _ = -1LL; ..END.
1370: 0a 2f 2a 0d 0a 43 41 53 45 28 35 29 0d 0a 09 73 ./*..CASE(5)...s
1380: 74 72 69 6e 67 20 6d 61 70 5f 5b 5d 20 3d 20 3b tring map_[] = ;
1390: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
13a0: 69 6e 67 3e 20 6d 61 70 28 6d 61 70 5f 2c 20 6d ing> map(map_, m
13b0: 61 70 5f 2b 73 69 7a 65 6f 66 28 6d 61 70 5f 29 ap_+sizeof(map_)
13c0: 2f 73 69 7a 65 6f 66 28 2a 6d 61 70 5f 29 29 3b /sizeof(*map_));
13d0: 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 72 31 ...long long r1
13e0: 20 3d 20 4c 4c 3b 20 0d 0a 09 69 6e 74 20 63 31 = LL; ...int c1
13f0: 20 3d 20 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e = ; ...long lon
1400: 67 20 72 32 20 3d 20 4c 4c 3b 20 0d 0a 09 69 6e g r2 = LL; ...in
1410: 74 20 63 32 20 3d 20 3b 20 0d 0a 09 6c 6f 6e 67 t c2 = ; ...long
1420: 20 6c 6f 6e 67 20 5f 20 3d 20 4c 4c 3b 20 0d 0a long _ = LL; ..
1430: 45 4e 44 0d 0a 43 41 53 45 28 36 29 0d 0a 09 73 END..CASE(6)...s
1440: 74 72 69 6e 67 20 6d 61 70 5f 5b 5d 20 3d 20 3b tring map_[] = ;
1450: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1460: 69 6e 67 3e 20 6d 61 70 28 6d 61 70 5f 2c 20 6d ing> map(map_, m
1470: 61 70 5f 2b 73 69 7a 65 6f 66 28 6d 61 70 5f 29 ap_+sizeof(map_)
1480: 2f 73 69 7a 65 6f 66 28 2a 6d 61 70 5f 29 29 3b /sizeof(*map_));
1490: 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 72 31 ...long long r1
14a0: 20 3d 20 4c 4c 3b 20 0d 0a 09 69 6e 74 20 63 31 = LL; ...int c1
14b0: 20 3d 20 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e = ; ...long lon
14c0: 67 20 72 32 20 3d 20 4c 4c 3b 20 0d 0a 09 69 6e g r2 = LL; ...in
14d0: 74 20 63 32 20 3d 20 3b 20 0d 0a 09 6c 6f 6e 67 t c2 = ; ...long
14e0: 20 6c 6f 6e 67 20 5f 20 3d 20 4c 4c 3b 20 0d 0a long _ = LL; ..
14f0: 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 END..*/..}..// E
1500: 4e 44 20 43 55 54 20 48 45 52 45 0d 0a ND CUT HERE..