SRM464 Div2 Hard(1000) ColorfulMazeTwo
まず、迷路中の全ての英字を'#'に置き換えて迷路を解く。解ければ安全に迷路を抜ける確率は1である。次に、迷路中の'A'を'.'にその他の英字を'#'に置き換えて迷路を解く。解ければ安全に迷路を抜ける確率は少なくとも1-trap[0]/100である。同様に英字を'.'と'#'に置き換える全ての組み合わせについて迷路を解き、確率の最大値を返す。組み合わせは128通りしかない。
#include <string> #include <vector> using namespace std; class ColorfulMazeTwo { bool solve( vector<string> maze ); public: double getProbability( vector <string> maze, vector <int> trap ); }; double ColorfulMazeTwo::getProbability( vector <string> maze, vector <int> trap ) { double prob = 0; for ( int i=0; i<128; i++ ) { vector<string> m = maze; for ( int y=0; y<(int)m.size(); y++ ) for ( int x=0; x<(int)m[0].size(); x++ ) { char c = m[y][x]; if ( 'A' <= c && c <= 'G' ) m[y][x] = (i&1<<(c-'A'))==0 ? '#' : '.'; } if ( solve( m ) ) { double p = 1; for ( int j=0; j<7; j++ ) if ( (i&1<<j) != 0 ) p *= 1 - trap[j]/100.; prob = max( prob, p ); } } return prob; } // '#', '.', '$', '!' だけからなる迷路を解く bool ColorfulMazeTwo::solve( vector<string> maze ) { int h = (int)maze.size(); int w = (int)maze[0].size(); int dy[4] = { 1, 0, -1, 0 }; int dx[4] = { 0, 1, 0, -1 }; bool update; do { update = false; for ( int y=0; y<h; y++ ) for ( int x=0; x<w; x++ ) if ( maze[y][x] == '$' ) { for ( int d=0; d<4; d++ ) { int ty = y + dy[d]; int tx = x + dx[d]; if ( 0 <= ty && ty < h && 0 <= tx && tx < w ) { if ( maze[ty][tx] == '.' ) maze[ty][tx] = '$', update = true; if ( maze[ty][tx] == '!' ) return true; } } } } while ( update ); return false; }