SRM464 Div2 Hard(1000) ColorfulMazeTwo

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;
}