4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class ColorfulMaze { public: 4fd800b3a8 2011-02-23 kinaba: double getProbability(vector <string> maze, vector <int> trap) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: return solve(maze, trap, 0); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: typedef int vert; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double solve(const vector<string>& maze, const vector<int>& trap, int damage) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: const int H = maze.size(); 4fd800b3a8 2011-02-23 kinaba: const int W = maze[0].size(); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // R[i] == list of cells colored 'A'+i and reachable from '$' 4fd800b3a8 2011-02-23 kinaba: vector<vert> R[7]; 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: stack<vert> Q; 4fd800b3a8 2011-02-23 kinaba: vector<bool> V(H*W); 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<H; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<W; ++x) 4fd800b3a8 2011-02-23 kinaba: if( maze[y][x] == '$' ) 4fd800b3a8 2011-02-23 kinaba: {Q.push(y*W+x); V[y*W+x]=1;} 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: while( !Q.empty() ) { 4fd800b3a8 2011-02-23 kinaba: vert v=Q.top(); Q.pop(); 4fd800b3a8 2011-02-23 kinaba: int y=v/W, x=v%W; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int dy[]={-1,+1,0,0}, dx[]={0,0,-1,+1}; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<4; ++i) { 4fd800b3a8 2011-02-23 kinaba: int yy=y+dy[i], xx=x+dx[i],u=yy*W+xx; 4fd800b3a8 2011-02-23 kinaba: if( 0<=yy && yy<H && 0<=xx && xx<W && maze[yy][xx]!='#' && !V[u] ) { 4fd800b3a8 2011-02-23 kinaba: if( maze[yy][xx]=='!' ) 4fd800b3a8 2011-02-23 kinaba: return 1.0; 4fd800b3a8 2011-02-23 kinaba: V[u]=1; 4fd800b3a8 2011-02-23 kinaba: if( maze[yy][xx] == '.' ) 4fd800b3a8 2011-02-23 kinaba: Q.push(u); 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: R[maze[yy][xx]-'A'].push_back(u); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double pMax = 0.0; 4fd800b3a8 2011-02-23 kinaba: for(int k=0; k<7; ++k) if(!R[k].empty()) { 4fd800b3a8 2011-02-23 kinaba: double p = 0; // prob. to survive when you first step in the color 'A'+k 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<string> m = maze; 4fd800b3a8 2011-02-23 kinaba: { // the case it was not a trap 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<H; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<W; ++x) 4fd800b3a8 2011-02-23 kinaba: if(maze[y][x]=='A'+k) m[y][x] = '.'; 4fd800b3a8 2011-02-23 kinaba: else if(maze[y][x]=='$') m[y][x] = ".#"[damage]; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<R[k].size(); ++i) 4fd800b3a8 2011-02-23 kinaba: m[R[k][i]/W][R[k][i]%W] = '$'; 4fd800b3a8 2011-02-23 kinaba: p = (1-trap[k]/100.0) * solve(m, trap, damage); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: if( damage == 0 ) { // the case it was a trap 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<H; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<W; ++x) 4fd800b3a8 2011-02-23 kinaba: if(maze[y][x]=='A'+k && m[y][x]!='$') m[y][x] = '#'; 4fd800b3a8 2011-02-23 kinaba: p += (trap[k]/100.0) * solve(m, trap, damage+1); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: pMax = max(pMax, p); // take the maximum 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return pMax; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const double& Expected, const double& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, ColorfulMaze().getProbability(maze, trap));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = { ".$.", 4fd800b3a8 2011-02-23 kinaba: "A#B", 4fd800b3a8 2011-02-23 kinaba: "A#B", 4fd800b3a8 2011-02-23 kinaba: ".!." }; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = { 50, 40, 0, 0, 0, 0, 0 }; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.8; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = { ".$.", 4fd800b3a8 2011-02-23 kinaba: "A#B", 4fd800b3a8 2011-02-23 kinaba: "A#C", 4fd800b3a8 2011-02-23 kinaba: ".!." }; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = { 20, 70, 40, 0, 0, 0, 0 }; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.86; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = { "$A#", 4fd800b3a8 2011-02-23 kinaba: ".#.", 4fd800b3a8 2011-02-23 kinaba: "#B!" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = { 10, 10, 10, 10, 10, 10, 10 }; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = { "$A..", 4fd800b3a8 2011-02-23 kinaba: "##.A", 4fd800b3a8 2011-02-23 kinaba: "..B!" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = { 50, 50, 0, 0, 0, 0, 0 }; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.75; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = { "$C..", 4fd800b3a8 2011-02-23 kinaba: "##.A", 4fd800b3a8 2011-02-23 kinaba: "..B!" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = { 50, 50, 100, 0, 0, 0, 0 }; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.5; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = { ".$.D.E.F.G.!." }; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = { 10, 20, 30, 40, 50, 60, 70 }; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.23400000000000004; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(6) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = { "CC...AA", 4fd800b3a8 2011-02-23 kinaba: "C##.##A", 4fd800b3a8 2011-02-23 kinaba: "!.E.E.$", 4fd800b3a8 2011-02-23 kinaba: "D##.##B", 4fd800b3a8 2011-02-23 kinaba: "DD...BB" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = { 90, 90, 25, 50, 75, 0, 0 }; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.8125; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: /* 4fd800b3a8 2011-02-23 kinaba: CASE(7) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = {"#BGGCAG#B##EFEBFCBGFD#E##FA##BBF#BCADAFGG#CD#AGFAD", "#CGEGBFF#GECDCFF#FBDDAAG#DCCBBB#CC#BGCBDD##AEDAAG#", "E##E#GEBC#CC#GGAEDECBBA#BE#ECE#FAGEBFGD#BCADGF##D#", "DB##BDCABBBADAFGEDEEFBEFFEGEAGFBEFGDA#CE#AFA#DF#DD", "GEGG##AA#GAE##DDEFGFA#CEAEG#BBFGBBADBGCEDBABCBGFEF", "DCGECEDEC#E##BBBEGGFDDF#C##DC#EFCF#EE#FCAGBGAAGFEF", "GCAFCFEGDFCCC##CGFF#A#BAFEAD#D#FC#D##DAADAF#B#DEEE", "C#G###BD#FBG#E#D###GCGG#GGFBD#EEGBE#BCE#FF##AEDEE#", "CDA##AGBDFDE#FD#ACCC#GDBABF#CC#B#AEBFCFG#GFACBA#AB", "AA#CDFCACAFEEEA#ABAFDFEGAE#FADBFAECBBAF##BGGDBEFDF", "FABGDDEBDDCADAC#ECAG##CFDEA#FFA#DAA#CABCGBFCFA###A", "!FCFG#FACC#GABA#CGBFCBC#BGGDCAFDDCFDGADEGDGAB#F#AG", "CDEAE#E#DEDDDGFEFEE#DDDBCDDFF####FAG#FB#G#GB###EFC", "#AF##B#BGD#E#GGEEEC##FBEGBG#DGDCBBFBEGAF##ADGGA#GG", "GBBEDAFDFFCG#GADACCC###EDFCE#GBFD#BBAEAFC#BEDGAFBA", "G#FFEF#EFEEGDADAC#BA#DCB#EG#GADE##ABAEFCGDD##BB##B", "BF#C##BBCCCAEDCD##FA#ACA#FCFA#EDGAGEFECCBBGFCGDEEB", "DE#FEDFFDDCBA#AD#GDAE#BGAEGEBF#GEDGCF#DACA#DDBCGA#", "GAEBFCEF##E#EFC#BFC#GCGEFAD#GDB#DG#FBDD#FAG##ABEED", "GFGDFDDEFAGEBCBB#DCA##FEEA#GABGBBD#FEBDECF##A#BD#F", "##BGADFCA##B##EBEBADADCCFBDEFAF#C#GGAADE#D##ACGF#C", "ECF##DCCDEGCG#C#CG#EGE#B##ADD#ADA#BGCADECECBD#DD#B", "GDFEAEBG##GAGBBFBECGCBEACB##GDDFGGAEFEBCCEACDAE#A#", "B#G#D#BABEDGBC#BCBFC#DGEBE#B#BCDB#CBBDBAAAF###FD#F", "EFDCFAGG#GB##BEDGFF#BBCF#BEDCABCEFCGED#EFABBBCGBCB", "#GEB#ACECDCCFGFGDGABACCG#FGAAGGD#ED##FEFBDEF#C#FDE", "#BGEFEG#CDGBFBFDEC#DGFFB#B#GBFGBEGF###CDBDEA##BE#F", "CCGBCGF#E#BBEFF###GED#DEEE##E#B#EEG#FA#GBCEGBGGCEF", "A##DA#A#BADG#DDF#EC#BABDE#CAD#DFB#GFBAEBCGACGCA#B#", "DB###BAD#FDCGCD#EBGGEEGF#DAFGDEC#FCCAEFDBCDFA###BB", "#DCEEEEABG#GFADBDFDBABEGDAEFEC#D#F#ADECBEG#CFEDD##", "#CD#DD##D#BA#AB#CBB#DDEDGBDDDDECB#DGB#GCEG#AAEFBFA", "FB#E#GDCBFF#DGDDDG#DFCCAD##CBFGGFDDGDDFCBGADAEACFE", "B#FF#BE##GCEA#CDDGECCAB#BEDFGCF#CEEFC#EDD#DEBGA###", "FE#FGBA#DAFC#D#EC#FECBED#B#GB####AB#DCGECE#BEG#AGF", "##BDCF#DBEC#FCFBGEDDAAECFGDG#EF###ACEABGEEGAG##BA#", "FF#EAGG##A#DB#BBE#BFDDCDBD#GGFAEEDBBEG#DDG##DFGGCA", "###E#BFGDBEA##EBCB#GG#CEBFGDBAGDF#CC#ABCFGAAEFABGC", "AGCGFBFBFGCE#ECCABCCBD#D##BBGACGCBFAD#DBDE#CE#EAD#", "AGGBGCEA##A#EFEF#FGAAFCB#EF#DGCFF#CBAAE#GFB#A#EFDD", "BEEDCDDGFFB#FB##FEFBFACBACA#EGDAEDGG#D###DECFEEAD#", "FDDBDDG#GGACG#F$#D#FEECF##FDCGAF#CGDEGC#GD##ABFEF#", "GBDDAB#BDDFGDBDDC#BABBGEGDAAG#FEDCAGGA#FDEC#ADGAED", "D#B#GBABD##AE#DD##A#CG#DF#AC#ABDDEBGEBA#A#FCDCAGDF", "DDD#FEFBCBFADADEBEF#FBEF#BAGFBD#GE#CFGG#CABGDGB#CF", "DGEGDDAE#F##C#DDF#DGEABCG#CFCF#FABFG#GEB#DG#EDECDE", "CCFEEB#A###AEB##GFB#FA#EDD#E#FAD#DB#ECFD#A#EFAG###", "CBEDEEG#FC##D##FBEEFEEA##ECADB#BFC#BDDDGDDGGEAEFEE", "#DB#GG#CA#AFBFGCCDGDD#BG#A#C#DA#B#CAGEADF#BEAD#E#A", "FC#GBFDEFAFCG#C#F#ECDB##ABA##AEEACAAEEAD#AAD#CFFA#"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = {32, 65, 91, 81, 62, 45, 52}; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.009185498471999998; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: */ 4fd800b3a8 2011-02-23 kinaba: CASE(8) 4fd800b3a8 2011-02-23 kinaba: string maze_[] = {"#A####.F...##B..#.B.A#....#.#......#B###.#.#.####.", "###F....DD###.#F..#.#...#.#.##..#F....##..#...G.#.", "#F.D##..DDD....##.D..D#DF..##...#F......#.F#E##.#.", ".#.#.E.#..#...#.##F#.#.#.###F##F##..#####.#F..#.#.", "##.#F#B..B..D###D#...#.D.##F#F####CA.#...###A##...", "C.#B#.#..##..B####.#..##.#.#.#####.#...GD#.DC##..#", "##C###CC.#C.##...##..#..##.##.E..##.#####....##...", ".###EE...##.#E##..##D#D.#D#F###..#..C###.#..C.C...", "A####.#..A...A#.#.###.#.A#A####..####.#BD...D.#.#.", ".#..E..CC.#.C#.#.#.C...C....G#..GA..##.####.#...#.", "####.A.#..AA#..###.#B#G.EE##...#..#G#CC#..#.....#.", "C....#...#.F#.C#C###.#.....F#.#..#..#F#...#####..#", "F...#C##.#D###.#C#..C...#C...CD.D...D#.#D#.F....#A", ".##AA#G##..#GB##DD#.....##.DD##..#..AA###.A..####.", ".##.A...#.A#...#..#GE###.C##.#.#.#.F.###......####", "###F.F##..#####.......##FF#F#E#E.#E.#...##B##B####", "##..#B#BA###.A..#..#A.####.GDD..####DE##.#.E.#####", "#D###.#.#.##D..##FB#.E##ED.##..D##.####.#....#D#.#", "D#..##.#####.BA.###A#B.#.#.....##..#.####.#.#.#B..", "BBB#..####..D#..#.##.#..#..#...##...#..##.#D.##.A.", "..B.BD#E#.#.E.......E##....E..#..#CC.C#.###.#.#...", "####CC....#E#.E###..##E..#EE.####.#....#.DDCC..##.", "#....#.##E.#####..####..E#F##.#..F.##A#..#..###.##", ".#..#G#G.#..#.#G.G.##.##G#G#.####.G..G#..G###..#G.", "#G###.#...D#D####.F####..#F#A##.#.G.###D##..###A#A", ".##AB####.F..#C.CF.#.F##..#.AAAA.BBB.B.##B#..##...", ".#.#F#...C#G#.F#.G##G#.##.##..####.GG.#.GBB#.###.B", "...F##.#.#.#.FA.#A##..#..B#A###..#.##..#..#.#AA.#.", "##.......AEEE#.#E..#...###B#.....#.....##.#..B#.BF", "...F..#..$C###...G..###.G##..#..G#....G.#.##EE#B#.", "FFFF.G.F.#.F#..#.#..##C#.#..A##.#A.##..#A#..A##.A.", "B#.B.#F##.A...#A#DG...G.#..E##B##...#.#.A#CC##C..#", "##D..#F.G####..G##G..##.#######GG#..#.GG#.#A#A##.#", "#B..#.#.#..##.#G#..#EEE.E.###.###EG#.##..G###E#E..", "###.#.ED#..DF###.#.#..##.####...##AE###BB##..#.B#F", ".#F#.#..#..#####CC...##.C#CBB.#...##B#..D#AA#A..#.", "...BBFB.#B..B#B####BG..#.G.#.##.###.G###...#GA..#A", ".#C.CA##E##EF#DF#E.E.###E.#G..CC.#..##..#A.#.E##EE", "..#F#.#.#....#F##F#F#..##.###F..#..#.G#####GG#.##G", ".#...DE#..#.#.#####.#.###D.#D.D.#....D#B#B#..DA..A", "#..##.#.###A.F##...#.....F#F#....F##F#.###E###ED#C", "C...C#F.#A##.#..#..#....#F#B#..F##F.D..###.A###A.A", ".###..#D..#..##C.#....##..##......###E.#..##EE.F##", "..F.#D.#...##D#..D#..#.F#.C..##..#..#....C..#B.#..", "#...##...B.###..#BF#C..##...###.##.##.GBB..#....#F", "F.#.##.##.#..C..#..E.CC#...C#G...#.G..G.A..F#F.#..", "##..F#.#....F.###D##.#G.##.###..##GG####.....##GG.", "##..#....#GG#G.G.F..F#..#....#.##..##.#CC.#.BA.#.#", "#.#..##D#.##.#.##.#.#A#.C..####.....#..#.###C.#C.#", ".#C!##...C###.E...#.#..###...E#####E#.###F#F.###.."}; 4fd800b3a8 2011-02-23 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 4fd800b3a8 2011-02-23 kinaba: int trap_[] = {14, 22, 100, 34, 15, 33, 42}; 4fd800b3a8 2011-02-23 kinaba: vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.34491599999999994; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE