#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class ColorfulMaze { public:
double getProbability(vector <string> maze, vector <int> trap)
{
return solve(maze, trap, 0);
}
typedef int vert;
double solve(const vector<string>& maze, const vector<int>& trap, int damage)
{
const int H = maze.size();
const int W = maze[0].size();
// R[i] == list of cells colored 'A'+i and reachable from '$'
vector<vert> R[7];
{
stack<vert> Q;
vector<bool> V(H*W);
for(int y=0; y<H; ++y)
for(int x=0; x<W; ++x)
if( maze[y][x] == '$' )
{Q.push(y*W+x); V[y*W+x]=1;}
while( !Q.empty() ) {
vert v=Q.top(); Q.pop();
int y=v/W, x=v%W;
int dy[]={-1,+1,0,0}, dx[]={0,0,-1,+1};
for(int i=0; i<4; ++i) {
int yy=y+dy[i], xx=x+dx[i],u=yy*W+xx;
if( 0<=yy && yy<H && 0<=xx && xx<W && maze[yy][xx]!='#' && !V[u] ) {
if( maze[yy][xx]=='!' )
return 1.0;
V[u]=1;
if( maze[yy][xx] == '.' )
Q.push(u);
else
R[maze[yy][xx]-'A'].push_back(u);
}
}
}
}
double pMax = 0.0;
for(int k=0; k<7; ++k) if(!R[k].empty()) {
double p = 0; // prob. to survive when you first step in the color 'A'+k
vector<string> m = maze;
{ // the case it was not a trap
for(int y=0; y<H; ++y)
for(int x=0; x<W; ++x)
if(maze[y][x]=='A'+k) m[y][x] = '.';
else if(maze[y][x]=='$') m[y][x] = ".#"[damage];
for(int i=0; i<R[k].size(); ++i)
m[R[k][i]/W][R[k][i]%W] = '$';
p = (1-trap[k]/100.0) * solve(m, trap, damage);
}
if( damage == 0 ) { // the case it was a trap
for(int y=0; y<H; ++y)
for(int x=0; x<W; ++x)
if(maze[y][x]=='A'+k && m[y][x]!='$') m[y][x] = '#';
p += (trap[k]/100.0) * solve(m, trap, damage+1);
}
pMax = max(pMax, p); // take the maximum
}
return pMax;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, ColorfulMaze().getProbability(maze, trap));}
int main(){
CASE(0)
string maze_[] = { ".$.",
"A#B",
"A#B",
".!." };
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = { 50, 40, 0, 0, 0, 0, 0 };
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.8;
END
CASE(1)
string maze_[] = { ".$.",
"A#B",
"A#C",
".!." };
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = { 20, 70, 40, 0, 0, 0, 0 };
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.86;
END
CASE(2)
string maze_[] = { "$A#",
".#.",
"#B!" };
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = { 10, 10, 10, 10, 10, 10, 10 };
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.0;
END
CASE(3)
string maze_[] = { "$A..",
"##.A",
"..B!" };
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = { 50, 50, 0, 0, 0, 0, 0 };
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.75;
END
CASE(4)
string maze_[] = { "$C..",
"##.A",
"..B!" };
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = { 50, 50, 100, 0, 0, 0, 0 };
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.5;
END
CASE(5)
string maze_[] = { ".$.D.E.F.G.!." };
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = { 10, 20, 30, 40, 50, 60, 70 };
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.23400000000000004;
END
CASE(6)
string maze_[] = { "CC...AA",
"C##.##A",
"!.E.E.$",
"D##.##B",
"DD...BB" };
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = { 90, 90, 25, 50, 75, 0, 0 };
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.8125;
END
/*
CASE(7)
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#"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = {32, 65, 91, 81, 62, 45, 52};
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.009185498471999998;
END
*/
CASE(8)
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.###.."};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
int trap_[] = {14, 22, 100, 34, 15, 33, 42};
vector <int> trap(trap_, trap_+sizeof(trap_)/sizeof(*trap_));
double _ = 0.34491599999999994;
END
}
// END CUT HERE