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 74 75 70 6c 65 3e 0d 0a 75 73 69 6e 67 20 6e <tuple>..using n
0150: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
0160: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
0170: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0180: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0190: 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 54 77 69 73 P;....class Twis
01a0: 74 79 50 61 73 73 61 67 65 73 20 7b 20 70 75 62 tyPassages { pub
01b0: 6c 69 63 3a 0d 0a 09 76 65 63 74 6f 72 3c 69 6e lic:...vector<in
01c0: 74 3e 20 73 69 6d 69 6c 61 72 52 6f 6f 6d 73 28 t> similarRooms(
01d0: 76 65 63 74 6f 72 3c 73 74 72 69 6e 67 3e 20 6d vector<string> m
01e0: 61 7a 65 29 0d 0a 09 7b 0d 0a 09 09 6d 61 70 3c aze)...{....map<
01f0: 69 6e 74 2c 69 6e 74 3e 20 65 32 6f 3b 0d 0a 09 int,int> e2o;...
0200: 09 47 72 61 70 68 20 6f 72 67 20 3d 20 70 61 72 .Graph org = par
0210: 73 65 5f 67 72 61 70 68 28 6d 61 7a 65 29 3b 20 se_graph(maze);
0220: 2f 2f 20 6f 72 69 67 69 6e 61 6c 20 67 72 61 70 // original grap
0230: 68 0d 0a 09 09 47 72 61 70 68 20 65 78 67 20 3d h....Graph exg =
0240: 20 63 6f 6e 73 74 72 75 63 74 5f 65 78 74 65 6e construct_exten
0250: 64 65 64 5f 67 72 61 70 68 28 6f 72 67 2c 20 26 ded_graph(org, &
0260: 65 32 6f 29 3b 20 2f 2f 20 65 78 74 65 6e 64 65 e2o); // extende
0270: 64 20 67 72 61 70 68 0d 0a 09 09 47 72 6f 75 70 d graph....Group
0280: 73 20 67 72 6f 75 70 73 20 3d 20 67 72 6f 75 70 s groups = group
0290: 69 6e 67 28 65 78 67 29 3b 20 2f 2f 20 67 72 6f ing(exg); // gro
02a0: 75 70 69 6e 67 0d 0a 0d 0a 09 09 2f 2f 20 73 69 uping......// si
02b0: 6d 69 6c 61 72 5b 6f 76 5d 20 3d 20 73 65 74 20 milar[ov] = set
02c0: 6f 66 20 6e 6f 64 65 73 20 69 6e 64 69 73 74 69 of nodes indisti
02d0: 6e 67 75 69 73 68 61 62 6c 65 20 66 72 6f 6d 20 nguishable from
02e0: 6f 76 20 28 69 6e 20 6f 72 69 67 69 6e 61 6c 20 ov (in original
02f0: 67 72 61 70 68 29 0d 0a 09 09 76 65 63 74 6f 72 graph)....vector
0300: 3c 73 65 74 3c 69 6e 74 3e 3e 20 73 69 6d 69 6c <set<int>> simil
0310: 61 72 28 6d 61 7a 65 2e 73 69 7a 65 28 29 29 3b ar(maze.size());
0320: 0d 0a 09 09 66 6f 72 28 61 75 74 6f 26 20 65 5f ....for(auto& e_
0330: 67 72 70 3a 20 67 72 6f 75 70 73 29 20 7b 0d 0a grp: groups) {..
0340: 09 09 09 73 65 74 3c 69 6e 74 3e 20 6f 5f 67 72 ...set<int> o_gr
0350: 70 3b 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 65 p;.....for(int e
0360: 76 3a 20 65 5f 67 72 70 29 0d 0a 09 09 09 09 6f v: e_grp)......o
0370: 5f 67 72 70 2e 69 6e 73 65 72 74 28 65 32 6f 5b _grp.insert(e2o[
0380: 65 76 5d 29 3b 0d 0a 09 09 09 66 6f 72 28 69 6e ev]);.....for(in
0390: 74 20 6f 76 3a 20 6f 5f 67 72 70 29 0d 0a 09 09 t ov: o_grp)....
03a0: 09 09 73 69 6d 69 6c 61 72 5b 6f 76 5d 2e 69 6e ..similar[ov].in
03b0: 73 65 72 74 28 6f 5f 67 72 70 2e 62 65 67 69 6e sert(o_grp.begin
03c0: 28 29 2c 20 6f 5f 67 72 70 2e 65 6e 64 28 29 29 (), o_grp.end())
03d0: 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 2f 2f 20 73 ;....}......// s
03e0: 69 6d 69 6c 61 72 5b 6f 76 5d 2d 31 20 69 73 20 imilar[ov]-1 is
03f0: 74 68 65 20 61 6e 73 77 65 72 2e 0d 0a 09 09 76 the answer.....v
0400: 65 63 74 6f 72 3c 69 6e 74 3e 20 61 6e 73 77 65 ector<int> answe
0410: 72 28 6d 61 7a 65 2e 73 69 7a 65 28 29 29 3b 0d r(maze.size());.
0420: 0a 09 09 74 72 61 6e 73 66 6f 72 6d 28 73 69 6d ...transform(sim
0430: 69 6c 61 72 2e 62 65 67 69 6e 28 29 2c 20 73 69 ilar.begin(), si
0440: 6d 69 6c 61 72 2e 65 6e 64 28 29 2c 20 61 6e 73 milar.end(), ans
0450: 77 65 72 2e 62 65 67 69 6e 28 29 2c 0d 0a 09 09 wer.begin(),....
0460: 09 5b 5d 28 63 6f 6e 73 74 20 73 65 74 3c 69 6e .[](const set<in
0470: 74 3e 26 20 67 29 7b 72 65 74 75 72 6e 20 67 2e t>& g){return g.
0480: 73 69 7a 65 28 29 2d 31 3b 7d 29 3b 0d 0a 09 09 size()-1;});....
0490: 72 65 74 75 72 6e 20 61 6e 73 77 65 72 3b 0d 0a return answer;..
04a0: 09 7d 0d 0a 0d 0a 09 74 79 70 65 64 65 66 20 76 .}.....typedef v
04b0: 65 63 74 6f 72 3c 76 65 63 74 6f 72 3c 69 6e 74 ector<vector<int
04c0: 3e 3e 20 47 72 61 70 68 3b 0d 0a 09 47 72 61 70 >> Graph;...Grap
04d0: 68 20 70 61 72 73 65 5f 67 72 61 70 68 28 63 6f h parse_graph(co
04e0: 6e 73 74 20 76 65 63 74 6f 72 3c 73 74 72 69 6e nst vector<strin
04f0: 67 3e 26 20 6d 61 7a 65 29 0d 0a 09 7b 0d 0a 09 g>& maze)...{...
0500: 09 47 72 61 70 68 20 67 3b 0d 0a 09 09 66 6f 72 .Graph g;....for
0510: 28 61 75 74 6f 26 20 6d 3a 20 6d 61 7a 65 29 20 (auto& m: maze)
0520: 7b 0d 0a 09 09 09 73 74 72 69 6e 67 73 74 72 65 {.....stringstre
0530: 61 6d 20 73 73 28 6d 29 3b 0d 0a 09 09 09 67 2e am ss(m);.....g.
0540: 65 6d 70 6c 61 63 65 5f 62 61 63 6b 28 69 73 74 emplace_back(ist
0550: 72 65 61 6d 5f 69 74 65 72 61 74 6f 72 3c 69 6e ream_iterator<in
0560: 74 3e 28 73 73 29 2c 20 69 73 74 72 65 61 6d 5f t>(ss), istream_
0570: 69 74 65 72 61 74 6f 72 3c 69 6e 74 3e 28 29 29 iterator<int>())
0580: 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e ;....}....return
0590: 20 67 3b 0d 0a 09 7d 0d 0a 0d 0a 09 47 72 61 70 g;...}.....Grap
05a0: 68 20 63 6f 6e 73 74 72 75 63 74 5f 65 78 74 65 h construct_exte
05b0: 6e 64 65 64 5f 67 72 61 70 68 28 63 6f 6e 73 74 nded_graph(const
05c0: 20 47 72 61 70 68 26 20 6f 72 67 2c 20 6d 61 70 Graph& org, map
05d0: 3c 69 6e 74 2c 69 6e 74 3e 2a 20 65 32 6f 29 0d <int,int>* e2o).
05e0: 0a 09 7b 0d 0a 09 09 6d 61 70 3c 70 61 69 72 3c ..{....map<pair<
05f0: 69 6e 74 2c 69 6e 74 3e 2c 20 69 6e 74 3e 20 6f int,int>, int> o
0600: 32 65 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 76 2e;....for(int v
0610: 3d 30 2c 69 64 3d 30 3b 20 76 3c 6f 72 67 2e 73 =0,id=0; v<org.s
0620: 69 7a 65 28 29 3b 20 2b 2b 76 29 20 7b 0d 0a 09 ize(); ++v) {...
0630: 09 09 2f 2f 20 73 70 65 63 69 61 6c 20 68 61 6e ..// special han
0640: 64 6c 69 6e 67 20 66 6f 72 20 6f 75 74 64 65 67 dling for outdeg
0650: 20 3d 20 30 20 6e 6f 64 65 0d 0a 09 09 09 69 66 = 0 node.....if
0660: 28 6f 72 67 5b 76 5d 2e 73 69 7a 65 28 29 20 3d (org[v].size() =
0670: 3d 20 30 29 20 7b 0d 0a 09 09 09 09 28 2a 65 32 = 0) {......(*e2
0680: 6f 29 5b 69 64 5d 20 3d 20 76 3b 0d 0a 09 09 09 o)[id] = v;.....
0690: 09 6f 32 65 5b 6d 61 6b 65 5f 70 61 69 72 28 76 .o2e[make_pair(v
06a0: 2c 30 29 5d 20 3d 20 69 64 2b 2b 3b 0d 0a 09 09 ,0)] = id++;....
06b0: 09 7d 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 76 .}.....for(int v
06c0: 69 3d 30 3b 20 76 69 3c 6f 72 67 5b 76 5d 2e 73 i=0; vi<org[v].s
06d0: 69 7a 65 28 29 3b 20 2b 2b 76 69 29 20 7b 0d 0a ize(); ++vi) {..
06e0: 09 09 09 09 28 2a 65 32 6f 29 5b 69 64 5d 20 3d ....(*e2o)[id] =
06f0: 20 76 3b 0d 0a 09 09 09 09 6f 32 65 5b 6d 61 6b v;......o2e[mak
0700: 65 5f 70 61 69 72 28 76 2c 76 69 29 5d 20 3d 20 e_pair(v,vi)] =
0710: 69 64 2b 2b 3b 0d 0a 09 09 09 7d 0d 0a 09 09 7d id++;.....}....}
0720: 0d 0a 0d 0a 09 09 47 72 61 70 68 20 65 78 67 28 ......Graph exg(
0730: 6f 32 65 2e 73 69 7a 65 28 29 29 3b 0d 0a 09 09 o2e.size());....
0740: 6d 61 70 3c 70 61 69 72 3c 69 6e 74 2c 69 6e 74 map<pair<int,int
0750: 3e 2c 20 69 6e 74 3e 20 6e 6f 64 65 69 64 3b 0d >, int> nodeid;.
0760: 0a 09 09 66 6f 72 28 69 6e 74 20 76 3d 30 3b 20 ...for(int v=0;
0770: 76 3c 6f 72 67 2e 73 69 7a 65 28 29 3b 20 2b 2b v<org.size(); ++
0780: 76 29 0d 0a 09 09 66 6f 72 28 69 6e 74 20 76 69 v)....for(int vi
0790: 3d 30 3b 20 76 69 3c 6f 72 67 5b 76 5d 2e 73 69 =0; vi<org[v].si
07a0: 7a 65 28 29 3b 20 2b 2b 76 69 29 20 7b 0d 0a 09 ze(); ++vi) {...
07b0: 09 09 2f 2f 20 28 76 2c 76 69 29 20 3a 20 63 61 ..// (v,vi) : ca
07c0: 6d 65 20 74 6f 20 74 68 65 20 72 6f 6f 6d 20 76 me to the room v
07d0: 20 66 72 6f 6d 20 74 68 65 20 76 69 2d 74 68 20 from the vi-th
07e0: 72 6f 61 64 2e 0d 0a 09 09 09 66 6f 72 28 69 6e road......for(in
07f0: 74 20 6b 3d 30 3b 20 6b 3c 6f 72 67 5b 76 5d 2e t k=0; k<org[v].
0800: 73 69 7a 65 28 29 3b 20 2b 2b 6b 29 20 7b 0d 0a size(); ++k) {..
0810: 09 09 09 09 2f 2f 20 47 6f 20 6b 2d 74 68 20 72 ....// Go k-th r
0820: 6f 61 64 20 63 6c 6f 63 6b 77 69 73 65 20 66 72 oad clockwise fr
0830: 6f 6d 20 69 2d 74 68 2e 20 52 65 61 63 68 65 73 om i-th. Reaches
0840: 20 28 75 2c 75 69 29 2e 0d 0a 09 09 09 09 69 6e (u,ui).......in
0850: 74 20 75 20 3d 20 6f 72 67 5b 76 5d 5b 28 76 69 t u = org[v][(vi
0860: 2b 6b 29 20 25 20 6f 72 67 5b 76 5d 2e 73 69 7a +k) % org[v].siz
0870: 65 28 29 5d 3b 0d 0a 09 09 09 09 69 6e 74 20 75 e()];......int u
0880: 69 20 3d 20 66 69 6e 64 28 6f 72 67 5b 75 5d 2e i = find(org[u].
0890: 62 65 67 69 6e 28 29 2c 20 6f 72 67 5b 75 5d 2e begin(), org[u].
08a0: 65 6e 64 28 29 2c 20 76 29 20 2d 20 6f 72 67 5b end(), v) - org[
08b0: 75 5d 2e 62 65 67 69 6e 28 29 3b 0d 0a 09 09 09 u].begin();.....
08c0: 09 2f 2f 20 28 76 2c 76 69 29 2d 2d 6b 2d 2d 3e .// (v,vi)--k-->
08d0: 28 75 2c 75 69 29 0d 0a 09 09 09 09 65 78 67 5b (u,ui)......exg[
08e0: 6f 32 65 5b 6d 61 6b 65 5f 70 61 69 72 28 76 2c o2e[make_pair(v,
08f0: 76 69 29 5d 5d 2e 70 75 73 68 5f 62 61 63 6b 28 vi)]].push_back(
0900: 6f 32 65 5b 6d 61 6b 65 5f 70 61 69 72 28 75 2c o2e[make_pair(u,
0910: 75 69 29 5d 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 ui)]);.....}....
0920: 7d 0d 0a 09 09 72 65 74 75 72 6e 20 65 78 67 3b }....return exg;
0930: 0d 0a 09 7d 0d 0a 0d 0a 09 74 79 70 65 64 65 66 ...}.....typedef
0940: 20 73 65 74 3c 73 65 74 3c 69 6e 74 3e 3e 20 47 set<set<int>> G
0950: 72 6f 75 70 73 3b 0d 0a 09 47 72 6f 75 70 73 20 roups;...Groups
0960: 67 72 6f 75 70 69 6e 67 28 63 6f 6e 73 74 20 47 grouping(const G
0970: 72 61 70 68 26 20 47 29 0d 0a 09 7b 0d 0a 09 09 raph& G)...{....
0980: 2f 2f 20 22 72 65 76 65 72 73 65 5f 65 64 67 65 // "reverse_edge
0990: 5b 75 5d 5b 65 5d 20 68 61 73 20 76 22 20 3a 3d [u][e] has v" :=
09a0: 20 76 2d 2d 65 2d 2d 3e 75 0d 0a 09 09 63 6f 6e v--e-->u....con
09b0: 73 74 20 69 6e 74 20 4d 61 78 45 64 67 65 4e 75 st int MaxEdgeNu
09c0: 6d 20 3d 20 47 2e 73 69 7a 65 28 29 3b 0d 0a 09 m = G.size();...
09d0: 09 76 65 63 74 6f 72 3c 76 65 63 74 6f 72 3c 76 .vector<vector<v
09e0: 65 63 74 6f 72 3c 69 6e 74 3e 3e 3e 20 72 65 76 ector<int>>> rev
09f0: 65 72 73 65 5f 65 64 67 65 28 47 2e 73 69 7a 65 erse_edge(G.size
0a00: 28 29 2c 20 76 65 63 74 6f 72 3c 76 65 63 74 6f (), vector<vecto
0a10: 72 3c 69 6e 74 3e 3e 28 4d 61 78 45 64 67 65 4e r<int>>(MaxEdgeN
0a20: 75 6d 29 29 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 um));....for(int
0a30: 20 76 3d 30 3b 20 76 3c 47 2e 73 69 7a 65 28 29 v=0; v<G.size()
0a40: 3b 20 2b 2b 76 29 0d 0a 09 09 09 66 6f 72 28 69 ; ++v).....for(i
0a50: 6e 74 20 65 3d 30 3b 20 65 3c 47 5b 76 5d 2e 73 nt e=0; e<G[v].s
0a60: 69 7a 65 28 29 3b 20 2b 2b 65 29 0d 0a 09 09 09 ize(); ++e).....
0a70: 09 72 65 76 65 72 73 65 5f 65 64 67 65 5b 47 5b .reverse_edge[G[
0a80: 76 5d 5b 65 5d 5d 5b 65 5d 2e 70 75 73 68 5f 62 v][e]][e].push_b
0a90: 61 63 6b 28 76 29 3b 0d 0a 0d 0a 09 09 76 65 63 ack(v);......vec
0aa0: 74 6f 72 3c 69 6e 74 3e 20 67 72 6f 75 70 5f 69 tor<int> group_i
0ab0: 64 28 47 2e 73 69 7a 65 28 29 29 3b 0d 0a 09 09 d(G.size());....
0ac0: 6d 61 70 3c 69 6e 74 2c 20 73 65 74 3c 69 6e 74 map<int, set<int
0ad0: 3e 3e 20 67 72 6f 75 70 73 3b 0d 0a 09 09 69 6e >> groups;....in
0ae0: 74 20 66 72 65 73 68 5f 67 72 6f 75 70 5f 69 64 t fresh_group_id
0af0: 20 3d 20 30 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 = 0;....for(int
0b00: 20 76 3d 30 3b 20 76 3c 47 2e 73 69 7a 65 28 29 v=0; v<G.size()
0b10: 3b 20 2b 2b 76 29 20 7b 0d 0a 09 09 09 67 72 6f ; ++v) {.....gro
0b20: 75 70 73 5b 47 5b 76 5d 2e 73 69 7a 65 28 29 5d ups[G[v].size()]
0b30: 2e 69 6e 73 65 72 74 28 76 29 3b 0d 0a 09 09 09 .insert(v);.....
0b40: 67 72 6f 75 70 5f 69 64 5b 76 5d 20 3d 20 47 5b group_id[v] = G[
0b50: 76 5d 2e 73 69 7a 65 28 29 3b 0d 0a 09 09 09 66 v].size();.....f
0b60: 72 65 73 68 5f 67 72 6f 75 70 5f 69 64 20 3d 20 resh_group_id =
0b70: 6d 61 78 28 66 72 65 73 68 5f 67 72 6f 75 70 5f max(fresh_group_
0b80: 69 64 2c 20 67 72 6f 75 70 5f 69 64 5b 76 5d 2b id, group_id[v]+
0b90: 31 29 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 71 75 1);....}......qu
0ba0: 65 75 65 3c 73 65 74 3c 69 6e 74 3e 3e 20 70 61 eue<set<int>> pa
0bb0: 72 74 69 74 69 6f 6e 65 72 3b 0d 0a 09 09 66 6f rtitioner;....fo
0bc0: 72 28 61 75 74 6f 26 20 6b 76 3a 20 67 72 6f 75 r(auto& kv: grou
0bd0: 70 73 29 0d 0a 09 09 09 70 61 72 74 69 74 69 6f ps).....partitio
0be0: 6e 65 72 2e 70 75 73 68 28 6b 76 2e 73 65 63 6f ner.push(kv.seco
0bf0: 6e 64 29 3b 0d 0a 0d 0a 09 09 77 68 69 6c 65 28 nd);......while(
0c00: 21 70 61 72 74 69 74 69 6f 6e 65 72 2e 65 6d 70 !partitioner.emp
0c10: 74 79 28 29 29 0d 0a 09 09 7b 0d 0a 09 09 09 73 ty())....{.....s
0c20: 65 74 3c 69 6e 74 3e 20 50 20 3d 20 70 61 72 74 et<int> P = part
0c30: 69 74 69 6f 6e 65 72 2e 66 72 6f 6e 74 28 29 3b itioner.front();
0c40: 0d 0a 09 09 09 70 61 72 74 69 74 69 6f 6e 65 72 .....partitioner
0c50: 2e 70 6f 70 28 29 3b 0d 0a 0d 0a 09 09 09 66 6f .pop();.......fo
0c60: 72 28 69 6e 74 20 65 3d 30 3b 20 65 3c 4d 61 78 r(int e=0; e<Max
0c70: 45 64 67 65 4e 75 6d 3b 20 2b 2b 65 29 0d 0a 09 EdgeNum; ++e)...
0c80: 09 09 7b 0d 0a 09 09 09 09 6d 61 70 3c 69 6e 74 ..{......map<int
0c90: 2c 20 73 65 74 3c 69 6e 74 3e 3e 20 67 32 75 3b , set<int>> g2u;
0ca0: 0d 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 76 3a ......for(int v:
0cb0: 20 50 29 0d 0a 09 09 09 09 09 66 6f 72 28 69 6e P).......for(in
0cc0: 74 20 75 3a 20 72 65 76 65 72 73 65 5f 65 64 67 t u: reverse_edg
0cd0: 65 5b 76 5d 5b 65 5d 29 0d 0a 09 09 09 09 09 09 e[v][e])........
0ce0: 67 32 75 5b 67 72 6f 75 70 5f 69 64 5b 75 5d 5d g2u[group_id[u]]
0cf0: 2e 69 6e 73 65 72 74 28 75 29 3b 0d 0a 09 09 09 .insert(u);.....
0d00: 09 66 6f 72 28 61 75 74 6f 26 20 6b 76 3a 20 67 .for(auto& kv: g
0d10: 32 75 29 20 7b 0d 0a 09 09 09 09 09 69 6e 74 20 2u) {.......int
0d20: 67 69 64 20 3d 20 6b 76 2e 66 69 72 73 74 3b 0d gid = kv.first;.
0d30: 0a 09 09 09 09 09 73 65 74 3c 69 6e 74 3e 26 20 ......set<int>&
0d40: 65 6e 74 65 72 50 20 3d 20 6b 76 2e 73 65 63 6f enterP = kv.seco
0d50: 6e 64 3b 0d 0a 09 09 09 09 09 69 66 28 67 72 6f nd;.......if(gro
0d60: 75 70 73 5b 67 69 64 5d 2e 73 69 7a 65 28 29 20 ups[gid].size()
0d70: 21 3d 20 65 6e 74 65 72 50 2e 73 69 7a 65 28 29 != enterP.size()
0d80: 29 20 7b 0d 0a 09 09 09 09 09 09 66 6f 72 28 69 ) {........for(i
0d90: 6e 74 20 75 3a 20 65 6e 74 65 72 50 29 20 7b 0d nt u: enterP) {.
0da0: 0a 09 09 09 09 09 09 09 67 72 6f 75 70 5f 69 64 ........group_id
0db0: 5b 75 5d 20 3d 20 66 72 65 73 68 5f 67 72 6f 75 [u] = fresh_grou
0dc0: 70 5f 69 64 3b 0d 0a 09 09 09 09 09 09 09 67 72 p_id;.........gr
0dd0: 6f 75 70 73 5b 67 69 64 5d 2e 65 72 61 73 65 28 oups[gid].erase(
0de0: 75 29 3b 0d 0a 09 09 09 09 09 09 7d 0d 0a 09 09 u);........}....
0df0: 09 09 09 09 67 72 6f 75 70 73 5b 66 72 65 73 68 ....groups[fresh
0e00: 5f 67 72 6f 75 70 5f 69 64 2b 2b 5d 20 3d 20 65 _group_id++] = e
0e10: 6e 74 65 72 50 3b 0d 0a 09 09 09 09 09 09 70 61 nterP;........pa
0e20: 72 74 69 74 69 6f 6e 65 72 2e 70 75 73 68 28 65 rtitioner.push(e
0e30: 6e 74 65 72 50 2e 73 69 7a 65 28 29 20 3c 20 67 nterP.size() < g
0e40: 72 6f 75 70 73 5b 67 69 64 5d 2e 73 69 7a 65 28 roups[gid].size(
0e50: 29 20 3f 20 65 6e 74 65 72 50 20 3a 20 67 72 6f ) ? enterP : gro
0e60: 75 70 73 5b 67 69 64 5d 29 3b 0d 0a 09 09 09 09 ups[gid]);......
0e70: 09 7d 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 7d 0d .}......}.....}.
0e80: 0a 09 09 7d 0d 0a 0d 0a 09 09 47 72 6f 75 70 73 ...}......Groups
0e90: 20 72 65 73 75 6c 74 3b 0d 0a 09 09 66 6f 72 28 result;....for(
0ea0: 61 75 74 6f 26 20 6b 76 3a 20 67 72 6f 75 70 73 auto& kv: groups
0eb0: 29 0d 0a 09 09 09 72 65 73 75 6c 74 2e 69 6e 73 ).....result.ins
0ec0: 65 72 74 28 6b 76 2e 73 65 63 6f 6e 64 29 3b 0d ert(kv.second);.
0ed0: 0a 09 09 72 65 74 75 72 6e 20 72 65 73 75 6c 74 ...return result
0ee0: 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 ;...}..};....//
0ef0: 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 0d 0a BEGIN CUT HERE..
0f00: 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d 65 3e #include <ctime>
0f10: 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 5f 74 ..double start_t
0f20: 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 6d 65 ime; string time
0f30: 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e 67 73 r().. { ostrings
0f40: 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 tream os; os <<
0f50: 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 6c 6f " (" << int((clo
0f60: 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d 65 29 ck()-start_time)
0f70: 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 43 2a /CLOCKS_PER_SEC*
0f80: 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 63 29 1000) << " msec)
0f90: 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 "; return os.str
0fa0: 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 65 3c (); }..template<
0fb0: 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 74 72 typename T> ostr
0fc0: 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c 3c 28 eam& operator<<(
0fd0: 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 6f 6e ostream& os, con
0fe0: 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 76 29 st vector<T>& v)
0ff0: 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b .. { os << "{ ";
1000: 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e 61 6d .. for(typenam
1010: 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e e vector<T>::con
1020: 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 3d 76 st_iterator it=v
1030: 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 76 2e .begin(); it!=v.
1040: 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 20 20 end(); ++it)..
1050: 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a os << '\"' << *
1060: 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 28 69 it << '\"' << (i
1070: 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f 20 22 t+1==v.end() ? "
1080: 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 3c 3c " : ", "); os <<
1090: 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 " }"; return os
10a0: 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 66 79 ; }..void verify
10b0: 5f 63 61 73 65 28 63 6f 6e 73 74 20 76 65 63 74 _case(const vect
10c0: 6f 72 20 3c 69 6e 74 3e 26 20 45 78 70 65 63 74 or <int>& Expect
10d0: 65 64 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 ed, const vector
10e0: 20 3c 69 6e 74 3e 26 20 52 65 63 65 69 76 65 64 <int>& Received
10f0: 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 ) {.. bool ok =
1100: 28 45 78 70 65 63 74 65 64 20 3d 3d 20 52 65 63 (Expected == Rec
1110: 65 69 76 65 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 eived);.. if(ok)
1120: 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 cerr << "PASSED
1130: 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 " << timer() <<
1140: 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 65 endl; else { ce
1150: 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c rr << "FAILED" <
1160: 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 < timer() << end
1170: 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c 74 l;.. cerr << "\t
1180: 6f 3a 20 22 20 3c 3c 20 45 78 70 65 63 74 65 64 o: " << Expected
1190: 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 78 << endl << "\tx
11a0: 3a 20 22 20 3c 3c 20 52 65 63 65 69 76 65 64 20 : " << Received
11b0: 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 << endl; } }..#d
11c0: 65 66 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 efine CASE(N) {c
11d0: 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 err << "Test Cas
11e0: 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e e #" << N << "..
11f0: 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 ." << flush; sta
1200: 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b rt_time=clock();
1210: 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 ..#define END. v
1220: 65 72 69 66 79 5f 63 61 73 65 28 5f 2c 20 54 77 erify_case(_, Tw
1230: 69 73 74 79 50 61 73 73 61 67 65 73 28 29 2e 73 istyPassages().s
1240: 69 6d 69 6c 61 72 52 6f 6f 6d 73 28 6d 61 7a 65 imilarRooms(maze
1250: 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 ));}..int main()
1260: 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 73 {....CASE(0)...s
1270: 74 72 69 6e 67 20 6d 61 7a 65 5f 5b 5d 20 3d 20 tring maze_[] =
1280: 7b 22 31 20 32 20 33 22 2c 20 22 30 22 2c 20 22 {"1 2 3", "0", "
1290: 30 22 2c 20 22 30 22 7d 3b 0d 0a 09 20 20 76 65 0", "0"};... ve
12a0: 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 6d 61 ctor <string> ma
12b0: 7a 65 28 6d 61 7a 65 5f 2c 20 6d 61 7a 65 5f 2b ze(maze_, maze_+
12c0: 73 69 7a 65 6f 66 28 6d 61 7a 65 5f 29 2f 73 69 sizeof(maze_)/si
12d0: 7a 65 6f 66 28 2a 6d 61 7a 65 5f 29 29 3b 20 0d zeof(*maze_)); .
12e0: 0a 09 69 6e 74 20 5f 5f 5b 5d 20 3d 20 7b 30 2c ..int __[] = {0,
12f0: 20 32 2c 20 32 2c 20 32 20 7d 3b 0d 0a 09 20 20 2, 2, 2 };...
1300: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 5f 28 5f vector <int> _(_
1310: 5f 2c 20 5f 5f 2b 73 69 7a 65 6f 66 28 5f 5f 29 _, __+sizeof(__)
1320: 2f 73 69 7a 65 6f 66 28 2a 5f 5f 29 29 3b 20 0d /sizeof(*__)); .
1330: 0a 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 .END..CASE(1)...
1340: 73 74 72 69 6e 67 20 6d 61 7a 65 5f 5b 5d 20 3d string maze_[] =
1350: 20 7b 22 31 20 32 20 33 22 2c 20 22 30 22 2c 20 {"1 2 3", "0",
1360: 22 30 22 2c 20 22 30 20 34 22 2c 20 22 33 22 7d "0", "0 4", "3"}
1370: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 ;... vector <st
1380: 72 69 6e 67 3e 20 6d 61 7a 65 28 6d 61 7a 65 5f ring> maze(maze_
1390: 2c 20 6d 61 7a 65 5f 2b 73 69 7a 65 6f 66 28 6d , maze_+sizeof(m
13a0: 61 7a 65 5f 29 2f 73 69 7a 65 6f 66 28 2a 6d 61 aze_)/sizeof(*ma
13b0: 7a 65 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 5f ze_)); ...int __
13c0: 5b 5d 20 3d 20 7b 30 2c 20 30 2c 20 30 2c 20 30 [] = {0, 0, 0, 0
13d0: 2c 20 30 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f , 0 };... vecto
13e0: 72 20 3c 69 6e 74 3e 20 5f 28 5f 5f 2c 20 5f 5f r <int> _(__, __
13f0: 2b 73 69 7a 65 6f 66 28 5f 5f 29 2f 73 69 7a 65 +sizeof(__)/size
1400: 6f 66 28 2a 5f 5f 29 29 3b 20 0d 0a 45 4e 44 0d of(*__)); ..END.
1410: 0a 43 41 53 45 28 32 29 0d 0a 09 73 74 72 69 6e .CASE(2)...strin
1420: 67 20 6d 61 7a 65 5f 5b 5d 20 3d 20 7b 22 31 20 g maze_[] = {"1
1430: 32 20 33 22 2c 20 22 30 22 2c 20 22 30 22 2c 20 2 3", "0", "0",
1440: 22 30 20 34 22 2c 20 22 33 22 2c 0d 0a 20 22 36 "0 4", "3",.. "6
1450: 20 37 20 38 22 2c 20 22 35 22 2c 20 22 35 22 2c 7 8", "5", "5",
1460: 20 22 35 20 39 22 2c 20 22 38 22 7d 3b 0d 0a 09 "5 9", "8"};...
1470: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
1480: 3e 20 6d 61 7a 65 28 6d 61 7a 65 5f 2c 20 6d 61 > maze(maze_, ma
1490: 7a 65 5f 2b 73 69 7a 65 6f 66 28 6d 61 7a 65 5f ze_+sizeof(maze_
14a0: 29 2f 73 69 7a 65 6f 66 28 2a 6d 61 7a 65 5f 29 )/sizeof(*maze_)
14b0: 29 3b 20 0d 0a 09 69 6e 74 20 5f 5f 5b 5d 20 3d ); ...int __[] =
14c0: 20 7b 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 2c {1, 1, 1, 1, 1,
14d0: 20 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 20 7d 1, 1, 1, 1, 1 }
14e0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
14f0: 74 3e 20 5f 28 5f 5f 2c 20 5f 5f 2b 73 69 7a 65 t> _(__, __+size
1500: 6f 66 28 5f 5f 29 2f 73 69 7a 65 6f 66 28 2a 5f of(__)/sizeof(*_
1510: 5f 29 29 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 _)); ..END..CASE
1520: 28 33 29 0d 0a 09 73 74 72 69 6e 67 20 6d 61 7a (3)...string maz
1530: 65 5f 5b 5d 20 3d 20 7b 22 31 20 32 20 33 20 34 e_[] = {"1 2 3 4
1540: 22 2c 20 20 22 30 22 2c 20 22 30 20 35 22 2c 20 ", "0", "0 5",
1550: 20 22 30 22 2c 20 22 36 20 30 22 2c 20 20 22 32 "0", "6 0", "2
1560: 22 2c 20 22 34 22 2c 0d 0a 22 38 20 31 30 20 39 ", "4",.."8 10 9
1570: 20 31 31 22 2c 20 22 37 22 2c 20 22 37 20 31 32 11", "7", "7 12
1580: 22 2c 20 22 37 22 2c 20 22 31 33 20 37 22 2c 20 ", "7", "13 7",
1590: 22 39 22 2c 20 22 31 31 22 7d 3b 0d 0a 09 20 20 "9", "11"};...
15a0: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
15b0: 6d 61 7a 65 28 6d 61 7a 65 5f 2c 20 6d 61 7a 65 maze(maze_, maze
15c0: 5f 2b 73 69 7a 65 6f 66 28 6d 61 7a 65 5f 29 2f _+sizeof(maze_)/
15d0: 73 69 7a 65 6f 66 28 2a 6d 61 7a 65 5f 29 29 3b sizeof(*maze_));
15e0: 20 0d 0a 09 69 6e 74 20 5f 5f 5b 5d 20 3d 20 7b ...int __[] = {
15f0: 30 2c 20 31 2c 20 31 2c 20 31 2c 20 31 2c 20 31 0, 1, 1, 1, 1, 1
1600: 2c 20 31 2c 20 30 2c 20 30 2c 20 30 2c 20 30 2c , 1, 0, 0, 0, 0,
1610: 20 30 2c 20 30 2c 20 30 20 7d 3b 0d 0a 09 20 20 0, 0, 0 };...
1620: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 5f 28 5f vector <int> _(_
1630: 5f 2c 20 5f 5f 2b 73 69 7a 65 6f 66 28 5f 5f 29 _, __+sizeof(__)
1640: 2f 73 69 7a 65 6f 66 28 2a 5f 5f 29 29 3b 20 0d /sizeof(*__)); .
1650: 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 0d 0a 09 .END..CASE(4)...
1660: 73 74 72 69 6e 67 20 6d 61 7a 65 5f 5b 5d 20 3d string maze_[] =
1670: 20 7b 22 31 20 32 22 2c 20 22 32 20 30 22 2c 20 {"1 2", "2 0",
1680: 22 30 20 31 22 2c 20 22 34 20 36 22 2c 20 22 35 "0 1", "4 6", "5
1690: 20 33 22 2c 20 22 36 20 34 22 2c 20 22 33 20 35 3", "6 4", "3 5
16a0: 22 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c "};... vector <
16b0: 73 74 72 69 6e 67 3e 20 6d 61 7a 65 28 6d 61 7a string> maze(maz
16c0: 65 5f 2c 20 6d 61 7a 65 5f 2b 73 69 7a 65 6f 66 e_, maze_+sizeof
16d0: 28 6d 61 7a 65 5f 29 2f 73 69 7a 65 6f 66 28 2a (maze_)/sizeof(*
16e0: 6d 61 7a 65 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 maze_)); ...int
16f0: 5f 5f 5b 5d 20 3d 20 7b 36 2c 20 36 2c 20 36 2c __[] = {6, 6, 6,
1700: 20 36 2c 20 36 2c 20 36 2c 20 36 20 7d 3b 0d 0a 6, 6, 6, 6 };..
1710: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1720: 5f 28 5f 5f 2c 20 5f 5f 2b 73 69 7a 65 6f 66 28 _(__, __+sizeof(
1730: 5f 5f 29 2f 73 69 7a 65 6f 66 28 2a 5f 5f 29 29 __)/sizeof(*__))
1740: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 29 ; ..END..CASE(5)
1750: 0d 0a 09 73 74 72 69 6e 67 20 6d 61 7a 65 5f 5b ...string maze_[
1760: 5d 20 3d 20 7b 22 31 20 32 20 33 22 2c 20 22 34 ] = {"1 2 3", "4
1770: 20 35 20 30 22 2c 20 22 36 20 37 20 30 22 2c 20 5 0", "6 7 0",
1780: 22 38 20 39 20 30 22 2c 20 22 31 30 20 31 31 20 "8 9 0", "10 11
1790: 31 22 2c 20 22 31 32 20 31 33 20 31 22 2c 20 0d 1", "12 13 1", .
17a0: 0a 20 22 31 34 20 31 35 20 32 22 2c 20 22 31 36 . "14 15 2", "16
17b0: 20 31 37 20 32 22 2c 20 22 31 38 20 31 39 20 33 17 2", "18 19 3
17c0: 22 2c 20 22 32 30 20 32 31 20 33 22 2c 20 22 32 ", "20 21 3", "2
17d0: 32 20 32 33 20 34 22 2c 20 0d 0a 20 22 32 34 20 2 23 4", .. "24
17e0: 32 35 20 34 22 2c 20 22 32 36 20 32 37 20 35 22 25 4", "26 27 5"
17f0: 2c 20 22 32 38 20 32 39 20 35 22 2c 20 22 33 30 , "28 29 5", "30
1800: 20 33 31 20 36 22 2c 20 22 33 32 20 33 33 20 36 31 6", "32 33 6
1810: 22 2c 20 0d 0a 20 22 33 34 20 33 35 20 37 22 2c ", .. "34 35 7",
1820: 20 22 33 36 20 33 37 20 37 22 2c 20 22 33 38 20 "36 37 7", "38
1830: 33 39 20 38 22 2c 20 22 34 30 20 34 31 20 38 22 39 8", "40 41 8"
1840: 2c 20 22 34 32 20 34 33 20 39 22 2c 20 0d 0a 20 , "42 43 9", ..
1850: 22 34 34 20 34 35 20 39 22 2c 20 22 31 30 22 2c "44 45 9", "10",
1860: 20 22 31 30 22 2c 20 22 31 31 22 2c 20 22 31 31 "10", "11", "11
1870: 22 2c 20 22 31 32 22 2c 20 22 31 32 22 2c 20 22 ", "12", "12", "
1880: 31 33 22 2c 20 22 31 33 22 2c 0d 0a 20 22 31 34 13", "13",.. "14
1890: 22 2c 20 22 31 34 22 2c 20 22 31 35 22 2c 20 22 ", "14", "15", "
18a0: 31 35 22 2c 20 22 31 36 22 2c 20 22 31 36 22 2c 15", "16", "16",
18b0: 20 22 31 37 22 2c 20 22 31 37 22 2c 20 22 31 38 "17", "17", "18
18c0: 22 2c 20 22 31 38 22 2c 0d 0a 20 22 31 39 22 2c ", "18",.. "19",
18d0: 20 22 31 39 22 2c 20 22 32 30 22 2c 20 22 32 30 "19", "20", "20
18e0: 22 2c 20 22 32 31 22 2c 20 22 32 31 22 7d 3b 0d ", "21", "21"};.
18f0: 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 .. vector <stri
1900: 6e 67 3e 20 6d 61 7a 65 28 6d 61 7a 65 5f 2c 20 ng> maze(maze_,
1910: 6d 61 7a 65 5f 2b 73 69 7a 65 6f 66 28 6d 61 7a maze_+sizeof(maz
1920: 65 5f 29 2f 73 69 7a 65 6f 66 28 2a 6d 61 7a 65 e_)/sizeof(*maze
1930: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 5f 5b 5d _)); ...int __[]
1940: 20 3d 20 7b 30 2c 20 32 2c 20 32 2c 20 32 2c 20 = {0, 2, 2, 2,
1950: 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2, 2, 2, 2, 2, 2
1960: 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c , 2, 2, 2, 2, 2,
1970: 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 2, 2, 2, 2, 2,
1980: 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2, 2, 2, 2, 2, 2
1990: 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c , 2, 2, 2, 2, 2,
19a0: 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 2, 2, 2, 2, 2,
19b0: 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2c 20 32 2, 2, 2, 2, 2, 2
19c0: 2c 20 32 2c 20 32 2c 20 32 2c 20 32 20 7d 3b 0d , 2, 2, 2, 2 };.
19d0: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
19e0: 20 5f 28 5f 5f 2c 20 5f 5f 2b 73 69 7a 65 6f 66 _(__, __+sizeof
19f0: 28 5f 5f 29 2f 73 69 7a 65 6f 66 28 2a 5f 5f 29 (__)/sizeof(*__)
1a00: 29 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 36 ); ..END..CASE(6
1a10: 29 0d 0a 09 73 74 72 69 6e 67 20 6d 61 7a 65 5f )...string maze_
1a20: 5b 5d 20 3d 20 7b 22 33 38 20 37 20 39 20 38 20 [] = {"38 7 9 8
1a30: 34 33 20 34 38 20 33 30 20 34 31 20 35 20 32 32 43 48 30 41 5 22
1a40: 20 32 36 20 33 35 20 33 33 20 34 22 2c 20 22 31 26 35 33 4", "1
1a50: 34 20 33 39 20 32 35 20 33 35 20 33 30 20 34 35 4 39 25 35 30 45
1a60: 20 31 38 20 31 32 20 31 30 20 38 20 32 31 20 34 18 12 10 8 21 4
1a70: 36 20 32 32 20 33 37 20 32 30 22 2c 20 22 31 35 6 22 37 20", "15
1a80: 20 33 37 20 32 36 20 34 34 20 31 39 20 31 37 20 37 26 44 19 17
1a90: 33 39 20 31 36 20 37 20 31 38 20 34 35 20 33 36 39 16 7 18 45 36
1aa0: 20 32 30 20 34 32 20 32 34 22 2c 20 22 32 31 20 20 42 24", "21
1ab0: 34 33 20 32 36 20 38 20 32 38 20 31 30 20 34 20 43 26 8 28 10 4
1ac0: 34 38 20 32 35 20 34 36 20 34 39 20 33 31 20 33 48 25 46 49 31 3
1ad0: 37 20 32 37 20 31 35 22 2c 20 22 38 20 33 31 20 7 27 15", "8 31
1ae0: 33 30 20 33 20 30 20 33 36 20 34 31 20 35 20 33 30 3 0 36 41 5 3
1af0: 34 20 32 35 20 34 34 20 33 32 20 39 20 31 34 20 4 25 44 32 9 14
1b00: 32 32 22 2c 20 22 34 36 20 33 33 20 33 38 20 34 22", "46 33 38 4
1b10: 20 34 37 20 33 34 20 31 37 20 36 20 34 35 20 31 47 34 17 6 45 1
1b20: 30 20 34 31 20 34 38 20 33 31 20 34 33 20 30 22 0 41 48 31 43 0"
1b30: 2c 20 22 35 20 34 30 20 31 37 20 31 39 20 32 32 , "5 40 17 19 22
1b40: 20 34 33 20 31 38 20 34 37 20 33 31 20 39 20 37 43 18 47 31 9 7
1b50: 20 31 35 20 32 39 20 32 38 20 32 33 22 2c 20 22 15 29 28 23", "
1b60: 31 39 20 33 38 20 32 31 20 31 31 20 33 34 20 33 19 38 21 11 34 3
1b70: 31 20 39 20 30 20 34 38 20 33 30 20 34 34 20 32 1 9 0 48 30 44 2
1b80: 20 32 36 20 31 36 20 36 22 2c 20 22 34 38 20 31 26 16 6", "48 1
1b90: 32 20 33 20 34 39 20 30 20 34 31 20 31 20 32 38 2 3 49 0 41 1 28
1ba0: 20 33 35 20 34 30 20 33 36 20 34 20 32 39 20 33 35 40 36 4 29 3
1bb0: 33 20 34 33 22 2c 20 22 31 38 20 33 36 20 36 20 3 43", "18 36 6
1bc0: 34 37 20 32 36 20 33 37 20 32 37 20 32 32 20 30 47 26 37 27 22 0
1bd0: 20 34 36 20 32 33 20 34 31 20 34 20 32 34 20 37 46 23 41 4 24 7
1be0: 22 2c 20 22 34 32 20 31 33 20 33 35 20 32 38 20 ", "42 13 35 28
1bf0: 33 31 20 31 32 20 31 31 20 33 20 31 20 32 30 20 31 12 11 3 1 20
1c00: 31 36 20 34 35 20 31 39 20 34 30 20 35 22 2c 20 16 45 19 40 5",
1c10: 22 31 34 20 31 35 20 34 35 20 34 36 20 31 33 20 "14 15 45 46 13
1c20: 37 20 32 37 20 33 39 20 32 35 20 33 38 20 34 34 7 27 39 25 38 44
1c30: 20 31 37 20 31 36 20 31 30 20 34 33 22 2c 20 22 17 16 10 43", "
1c40: 34 38 20 38 20 31 35 20 34 32 20 34 37 20 31 30 48 8 15 42 47 10
1c50: 20 32 39 20 34 35 20 33 39 20 31 20 31 39 20 32 29 45 39 1 19 2
1c60: 35 20 34 34 20 33 32 20 32 36 22 2c 20 22 34 37 5 44 32 26", "47
1c70: 20 32 34 20 31 31 20 33 36 20 34 31 20 34 32 20 24 11 36 41 42
1c80: 31 36 20 33 38 20 33 37 20 32 30 20 33 32 20 33 16 38 37 20 32 3
1c90: 31 20 34 35 20 32 39 20 31 30 22 2c 20 22 33 31 1 45 29 10", "31
1ca0: 20 34 38 20 34 39 20 32 35 20 31 31 20 33 38 20 48 49 25 11 38
1cb0: 31 38 20 32 33 20 34 33 20 34 20 32 32 20 34 31 18 23 43 4 22 41
1cc0: 20 32 34 20 31 20 32 37 22 2c 20 22 33 32 20 33 24 1 27", "32 3
1cd0: 34 20 32 33 20 31 31 20 36 20 34 33 20 32 20 32 4 23 11 6 43 2 2
1ce0: 32 20 34 38 20 34 35 20 31 37 20 34 31 20 31 32 2 48 45 17 41 12
1cf0: 20 31 36 20 33 22 2c 20 22 37 20 34 36 20 31 38 16 3", "7 46 18
1d00: 20 32 38 20 32 30 20 31 39 20 34 33 20 33 31 20 28 20 19 43 31
1d10: 32 37 20 32 20 31 35 20 31 33 20 33 39 20 31 30 27 2 15 13 39 10
1d20: 20 31 31 22 2c 20 22 31 39 20 32 36 20 32 38 20 11", "19 26 28
1d30: 32 20 33 30 20 32 33 20 31 35 20 35 20 32 34 20 2 30 23 15 5 24
1d40: 34 37 20 32 35 20 31 38 20 36 20 34 32 20 31 31 47 25 18 6 42 11
1d50: 22 2c 20 22 32 36 20 36 20 32 34 20 34 36 20 31 ", "26 6 24 46 1
1d60: 37 20 34 32 20 34 35 20 31 34 20 31 36 20 39 20 7 42 45 14 16 9
1d70: 32 32 20 32 37 20 31 20 33 33 20 32 22 2c 20 22 22 27 1 33 2", "
1d80: 33 30 20 36 20 31 37 20 33 37 20 33 39 20 33 33 30 6 17 37 39 33
1d90: 20 34 39 20 32 20 32 31 20 34 36 20 31 36 20 32 49 2 21 46 16 2
1da0: 37 20 37 20 31 30 20 31 32 22 2c 20 22 31 33 20 7 7 10 12", "13
1db0: 33 32 20 34 31 20 31 20 33 39 20 31 36 20 34 32 32 41 1 39 16 42
1dc0: 20 32 37 20 32 20 33 33 20 34 30 20 32 34 20 34 27 2 33 40 24 4
1dd0: 35 20 34 38 20 31 30 22 2c 20 22 33 36 20 33 37 5 48 10", "36 37
1de0: 20 34 31 20 31 20 33 30 20 37 20 32 33 20 33 35 41 1 30 7 23 35
1df0: 20 34 30 20 34 34 20 32 36 20 34 37 20 33 39 20 40 44 26 47 39
1e00: 33 20 31 39 22 2c 20 22 31 34 20 36 20 32 33 20 3 19", "14 6 23
1e10: 34 30 20 30 20 34 33 20 39 20 32 39 20 31 20 31 40 0 43 9 29 1 1
1e20: 38 20 33 31 20 31 35 20 32 38 20 33 34 20 34 22 8 31 15 28 34 4"
1e30: 2c 20 22 33 30 20 31 34 20 36 20 32 38 20 33 34 , "30 14 6 28 34
1e40: 20 32 32 20 34 38 20 39 20 34 30 20 32 31 20 34 22 48 9 40 21 4
1e50: 32 20 31 37 20 31 35 20 33 37 20 33 32 22 2c 20 2 17 15 37 32",
1e60: 22 34 38 20 34 30 20 34 34 20 32 36 20 39 20 32 "48 40 44 26 9 2
1e70: 30 20 31 33 20 34 33 20 31 37 20 32 20 31 38 20 0 13 43 17 2 18
1e80: 32 39 20 31 34 20 34 32 20 34 36 22 2c 20 22 33 29 14 42 46", "3
1e90: 32 20 31 32 20 34 33 20 31 20 31 37 20 33 39 20 2 12 43 1 17 39
1ea0: 32 39 20 31 34 20 33 20 33 36 20 31 31 20 34 30 29 14 3 36 11 40
1eb0: 20 34 20 34 39 20 33 33 22 2c 20 22 30 20 37 20 4 49 33", "0 7
1ec0: 33 39 20 33 20 31 32 20 34 39 20 33 38 20 33 36 39 3 12 49 38 36
1ed0: 20 32 31 20 32 39 20 31 38 20 31 37 20 39 20 32 21 29 18 17 9 2
1ee0: 20 32 34 22 2c 20 22 32 39 20 32 38 20 33 38 20 24", "29 28 38
1ef0: 31 36 20 31 38 20 34 36 20 39 20 33 20 33 35 20 16 18 46 9 3 35
1f00: 33 36 20 34 30 20 32 30 20 31 34 20 31 31 20 31 36 40 20 14 11 1
1f10: 39 22 2c 20 22 33 33 20 33 39 20 33 35 20 33 38 9", "33 39 35 38
1f20: 20 33 20 36 20 32 32 20 31 30 20 32 33 20 31 37 3 6 22 10 23 17
1f30: 20 32 37 20 34 36 20 31 36 20 38 20 34 32 22 2c 27 46 16 8 42",
1f40: 20 22 31 33 20 32 36 20 32 35 20 33 37 20 33 33 "13 26 25 37 33
1f50: 20 34 34 20 31 32 20 34 38 20 36 20 34 31 20 34 44 12 48 6 41 4
1f60: 36 20 32 34 20 38 20 32 32 20 32 37 22 2c 20 22 6 24 8 22 27", "
1f70: 33 34 20 34 31 20 33 38 20 32 31 20 30 20 31 39 34 41 38 21 0 19
1f80: 20 32 33 20 34 20 37 20 34 39 20 31 20 34 34 20 23 4 7 49 1 44
1f90: 31 37 20 34 30 20 33 35 22 2c 20 22 33 20 31 34 17 40 35", "3 14
1fa0: 20 33 32 20 34 20 35 20 33 37 20 37 20 36 20 31 32 4 5 37 7 6 1
1fb0: 33 20 31 30 20 32 32 20 31 36 20 34 34 20 34 37 3 10 22 16 44 47
1fc0: 20 34 39 22 2c 20 22 31 35 20 34 20 31 33 20 33 49", "15 4 13 3
1fd0: 31 20 33 38 20 32 33 20 34 32 20 32 30 20 31 32 1 38 23 42 20 12
1fe0: 20 34 36 20 33 35 20 32 35 20 34 33 20 33 34 20 46 35 25 43 34
1ff0: 33 37 22 2c 20 22 33 39 20 34 34 20 31 39 20 30 37", "39 44 19 0
2000: 20 31 38 20 32 38 20 32 30 20 33 37 20 32 39 20 18 28 20 37 29
2010: 34 38 20 38 20 34 35 20 32 35 20 35 20 33 34 22 48 8 45 25 5 34"
2020: 2c 20 22 33 36 20 34 34 20 34 37 20 37 20 31 35 , "36 44 47 7 15
2030: 20 34 20 33 33 20 33 30 20 34 32 20 33 32 20 32 4 33 30 42 32 2
2040: 32 20 34 30 20 35 20 32 33 20 34 31 22 2c 20 22 2 40 5 23 41", "
2050: 34 30 20 32 37 20 34 32 20 38 20 34 35 20 33 32 40 27 42 8 45 32
2060: 20 31 30 20 30 20 32 38 20 31 20 34 39 20 34 36 10 0 28 1 49 46
2070: 20 33 30 20 34 37 20 32 31 22 2c 20 22 34 20 32 30 47 21", "4 2
2080: 20 32 31 20 34 37 20 38 20 33 38 20 32 37 20 34 21 47 8 38 27 4
2090: 35 20 33 39 20 31 33 20 34 39 20 32 36 20 39 20 5 39 13 49 26 9
20a0: 32 35 20 33 34 22 2c 20 22 34 32 20 32 31 20 33 25 34", "42 21 3
20b0: 31 20 32 39 20 31 33 20 34 37 20 33 32 20 33 20 1 29 13 47 32 3
20c0: 39 20 33 33 20 32 20 32 33 20 34 35 20 31 20 31 9 33 2 23 45 1 1
20d0: 39 22 2c 20 22 30 20 34 33 20 37 20 32 38 20 34 9", "0 43 7 28 4
20e0: 34 20 31 33 20 32 37 20 33 32 20 34 39 20 31 34 4 13 27 32 49 14
20f0: 20 33 36 20 31 31 20 35 20 33 30 20 32 36 22 2c 36 11 5 30 26",
2100: 20 22 31 36 20 33 36 20 32 31 20 32 30 20 31 32 "16 36 21 20 12
2110: 20 34 38 20 32 36 20 34 31 20 32 20 31 31 20 32 48 26 41 2 11 2
2120: 38 20 33 33 20 31 20 31 39 20 32 35 22 2c 20 22 8 33 1 19 25", "
2130: 38 20 32 32 20 31 30 20 36 20 33 35 20 32 30 20 8 22 10 6 35 20
2140: 32 35 20 32 33 20 34 31 20 32 37 20 33 30 20 32 25 23 41 27 30 2
2150: 34 20 34 34 20 33 34 20 32 31 22 2c 20 22 31 33 4 44 34 21", "13
2160: 20 32 39 20 33 39 20 31 35 20 30 20 33 30 20 34 29 39 15 0 30 4
2170: 30 20 32 30 20 34 20 35 20 33 34 20 31 34 20 38 0 20 4 5 34 14 8
2180: 20 39 20 32 31 22 2c 20 22 32 38 20 31 30 20 33 9 21", "28 10 3
2190: 32 20 31 37 20 33 34 20 33 37 20 31 33 20 32 20 2 17 34 37 13 2
21a0: 31 38 20 32 30 20 31 32 20 32 34 20 33 35 20 34 18 20 12 24 35 4
21b0: 39 20 32 33 22 2c 20 22 35 20 34 37 20 32 35 20 9 23", "5 47 25
21c0: 32 34 20 31 31 20 38 20 31 34 20 33 38 20 31 36 24 11 8 14 38 16
21d0: 20 36 20 33 32 20 31 35 20 32 32 20 33 20 30 22 6 32 15 22 3 0"
21e0: 2c 20 22 34 30 20 33 38 20 33 30 20 32 31 20 33 , "40 38 30 21 3
21f0: 31 20 34 36 20 33 34 20 32 39 20 31 31 20 33 33 1 46 34 29 11 33
2200: 20 34 20 31 32 20 32 34 20 32 20 37 22 2c 20 22 4 12 24 2 7", "
2210: 33 35 20 34 39 20 33 36 20 31 30 20 31 32 20 31 35 49 36 10 12 1
2220: 31 20 33 37 20 31 38 20 33 33 20 32 20 32 30 20 1 37 18 33 2 20
2230: 31 20 31 33 20 31 35 20 35 22 2c 20 22 33 20 32 1 13 15 5", "3 2
2240: 38 20 33 35 20 31 20 31 39 20 39 20 31 38 20 32 8 35 1 19 9 18 2
2250: 37 20 33 32 20 34 34 20 32 34 20 31 31 20 32 39 7 32 44 24 11 29
2260: 20 31 36 20 35 22 2c 20 22 39 20 34 33 20 36 20 16 5", "9 43 6
2270: 33 31 20 31 32 20 31 33 20 33 35 20 32 31 20 33 31 12 13 35 21 3
2280: 36 20 35 20 34 39 20 33 34 20 34 38 20 31 37 20 6 5 49 34 48 17
2290: 33 37 22 2c 20 22 32 34 20 33 33 20 35 20 38 20 37", "24 33 5 8
22a0: 31 35 20 31 32 20 34 37 20 32 39 20 30 20 37 20 15 12 47 29 0 7
22b0: 32 33 20 32 30 20 31 34 20 33 39 20 33 22 2c 20 23 20 14 39 3",
22c0: 22 31 39 20 33 20 31 34 20 38 20 33 38 20 34 37 "19 3 14 8 38 47
22d0: 20 33 30 20 33 36 20 33 35 20 32 35 20 33 31 20 30 36 35 25 31
22e0: 32 36 20 34 32 20 34 35 22 7d 3b 0d 0a 3b 0d 0a 26 42 45"};..;..
22f0: 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e . vector <strin
2300: 67 3e 20 6d 61 7a 65 28 6d 61 7a 65 5f 2c 20 6d g> maze(maze_, m
2310: 61 7a 65 5f 2b 73 69 7a 65 6f 66 28 6d 61 7a 65 aze_+sizeof(maze
2320: 5f 29 2f 73 69 7a 65 6f 66 28 2a 6d 61 7a 65 5f _)/sizeof(*maze_
2330: 29 29 3b 20 0d 0a 09 20 20 69 6e 74 20 5f 5f 5b )); ... int __[
2340: 5d 20 3d 20 7b 30 7d 3b 0d 0a 09 20 20 76 65 63 ] = {0};... vec
2350: 74 6f 72 20 3c 69 6e 74 3e 20 5f 28 5f 5f 2c 20 tor <int> _(__,
2360: 5f 5f 2b 73 69 7a 65 6f 66 28 5f 5f 29 2f 73 69 __+sizeof(__)/si
2370: 7a 65 6f 66 28 2a 5f 5f 29 29 3b 20 0d 0a 45 4e zeof(*__)); ..EN
2380: 44 0d 0a 2f 2a 0d 0a 43 41 53 45 28 37 29 0d 0a D../*..CASE(7)..
2390: 09 73 74 72 69 6e 67 20 6d 61 7a 65 5f 5b 5d 20 .string maze_[]
23a0: 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c = ;... vector <
23b0: 73 74 72 69 6e 67 3e 20 6d 61 7a 65 28 6d 61 7a string> maze(maz
23c0: 65 5f 2c 20 6d 61 7a 65 5f 2b 73 69 7a 65 6f 66 e_, maze_+sizeof
23d0: 28 6d 61 7a 65 5f 29 2f 73 69 7a 65 6f 66 28 2a (maze_)/sizeof(*
23e0: 6d 61 7a 65 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 maze_)); ...int
23f0: 5f 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 __[] = ;... vec
2400: 74 6f 72 20 3c 69 6e 74 3e 20 5f 28 5f 5f 2c 20 tor <int> _(__,
2410: 5f 5f 2b 73 69 7a 65 6f 66 28 5f 5f 29 2f 73 69 __+sizeof(__)/si
2420: 7a 65 6f 66 28 2a 5f 5f 29 29 3b 20 0d 0a 45 4e zeof(*__)); ..EN
2430: 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 D..*/..}..// END
2440: 20 43 55 54 20 48 45 52 45 0d 0a CUT HERE..