問題概説
string[] mazeで与えられたカラフルな迷路にいます。i番目の要素のj文字目が迷路の( i, j )座標に相当します。迷路には次のタイプがあります。
- # : 壁、通れない
- . : 通路、自由に通れる
- A-G : 色のついた通路、自由に通れる
- $ : 入り口
- ! : 出口
色のついた床は罠のある危険な床ですが、あなたは事前にどの色の床が危険であるか知りません。あなたの知っていることは、どの色が危険かという確率だけです。int[] trapが与えられていて、最初の要素はAが危険である確率で、以下同様です。罠の仕掛けられている床を踏むとダメージを受けます（訳注：罠にかかると死んでしまうようで失敗となります）。
迷路は四方に動くことができますが、斜めには動くことはできません。
問題
ダメージを受けないで迷路を脱出できる最大の確率を求めて下さい。
例1
{ ".$.",
"A#B",
"A#B",
".!." }
{ 50, 50, 0, 0, 0, 0, 0 }
Returns: 0.5
仮に左回りを選んだとします。Aに罠が仕掛けられている確率は50%です。もし罠が仕掛けられていていたら、Aを通過すると死んでしまいます。もし罠がなければ次のAも安全です。したがって左回りで生存する確率は50%です。右回りも同様に50%です。
例2
{ "$A#",
".#.",
"#B!" }
{ 10, 10, 10, 10, 10, 10, 10 }
Returns: 0.0
どのように歩いても出口に到達できないため、確率は0です。
例3
{ "$A..",
"##.A",
"..B!" }
{ 50, 50, 0, 0, 0, 0, 0 }
Returns: 0.5
Aを2回通るだけなので50%です。Bは通る必要はありません。
例4
{ "$C..",
"##.A",
"..B!" }
{ 50, 50, 100, 0, 0, 0, 0 }
Returns: 0.0
Cを必ず通り、Cには罠が100%仕掛けられているので生存確率は0%です。
例4
{ ".$.D.E.F.G.!." }
{ 10, 20, 30, 40, 50, 60, 70 }
Returns: 0.036000000000000004
D, E, F, Gを踏みますので、( 1 – 0.7 ) * ( 1 – 0.6 ) * ( 1 – 0.5 ) * ( 1 – 0.4 ) = 0.3 * 0.4 * 0.5 * 0.6 = 0.036です。
方針1：BFS（SystemTestで撃沈）
幅優先探索(BFS)で探索します。
ルートの記録
現在地、今までに通った経路（フラグ）、生存確率、トラップの発動確率（一度踏んだ色は0にしておく）を持ったlocation構造体を用意します。
初期化
location構造体を1つ用意して、スタート地点、トラップの発動確率（問題から与えられる）、現時点での生存率（初期値は1.00）を設定してキューにプッシュします。
whileループを回します。脱出条件はキューが空（もう探索すべき点がない）こと。
ループ内ですること
まずキューから1つlocationを取り出します。locationがゴールならこれ以上探索は要らないので、キューに何も追加せずcontinueします。その際に、今まで歩いてきたルートでの生存確率と、今までにチェックした最大の生存確率と比較して大きい方を残します。
上下左右の探索
上下左右をチェックして、壁ではない、範囲外ではない、今までに踏んでいないときは探索します。幅優先なので、新しいポイントをキューにプッシュして別の可能性を考えます。
実装例
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
struct location
{
int x;
int y;
double p;
bool flag[50][50];
vector <int> trap;
};
class ColorfulMazeTwo {
private:
vector <string> map;
int width;
int height;
public:
bool check( location &l )
{
if( l.x < 0 ) return false;
if( l.y < 0 ) return false;
if( l.x >= width ) return false;
if( l.y >= height ) return false;
if( map[l.y][l.x] == '#' ) return false;
if( l.flag[l.y][l.x] == true ) return false;
return true;
}
double getProbability(vector <string> maze, vector <int> trap)
{
double result = 0.0;
map = maze;
queue<location> que;
location l;
width = maze[0].length();
height = maze.size();
printf("width = %d\n",width);
printf("height = %d\n",height);
for( int i = 0; i < height; i++ )
{
int s = maze[i].find('$');
if( s == maze[i].npos ) continue;
l.x = s;
l.y = i;
l.p = 1.00;
l.trap = trap;
for( int x = 0; x < width; x++ )
for( int y = 0; y < height; y++ )
l.flag[y][x] = false;
que.push(l);
break;
}
while(!que.empty())
{
location newLocation;
l = que.front();
que.pop();
printf( "キューから(%d,%d)を取り出しました\n", l.x, l.y );
// 現在地の確認
char floor = map[l.y][l.x];
if( 'A' <= floor && floor <= 'G' )
{
int kind = floor - 'A';
double probability_of_survive = 1.00 - (l.trap[kind]/100.0);
l.p *= probability_of_survive;
l.trap[kind] = 0;
cout << floor << "を踏みました：生存確率" << l.p << endl;
}
// exit
if( floor == '!' )
{
if( result < l.p )
result = l.p;
puts("ゴールに到達しました");
printf( "Location(%d,%d)\n", l.x, l.y );
continue;
}
// can move left
newLocation = l;
newLocation.x--;
if( check(newLocation) )
{
newLocation.flag[l.y][l.x] = true;
printf("(%d,%d)をキューに入れました\n", newLocation.x, newLocation.y );
que.push(newLocation);
}
// can move right
newLocation = l;
newLocation.x++;
if( check(newLocation) )
{
newLocation.flag[l.y][l.x] = true;
printf("(%d,%d)をキューに入れました\n", newLocation.x, newLocation.y );
que.push(newLocation);
}
// can move up
newLocation = l;
newLocation.y--;
if( check(newLocation) )
{
newLocation.flag[l.y][l.x] = true;
printf("(%d,%d)をキューに入れました\n", newLocation.x, newLocation.y );
que.push(newLocation);
}
// can move up
newLocation = l;
newLocation.y++;
if( check(newLocation) )
{
newLocation.flag[l.y][l.x] = true;
printf("(%d,%d)をキューに入れました\n", newLocation.x, newLocation.y );
que.push(newLocation);
}
}
puts("キューが空になりました。");
printf("最大値は%lfです\n",result);
return result;
}
};
SystemTest
全部で25のテストケースのうち2つ通らないケースがありました。1つは
{"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDD$DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDD!DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD",
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD"},
{53, 12, 40, 75, 61, 64, 91}
で、もう1つも同様に広い部屋に放り出されるタイプです。こういう問題は幅優先で全域探索すると時間オーバーになってしまいます。
方針1：DFS（書きかけ）
幅優先探索で行き詰まったので、深さ優先探索を考えてみました。
事前に確率を計算しておく
トラップがA〜Gまでの7種類あることから、トラップを踏むパターンは2^7=128通りしかないことになります。したがって、例えばABCを踏むルートの確率は事前に計算できることになります。この確率を計算して、確率の高い順にソートします。
次に確率の高い順から深さ優先探索で到達可能か検証していきます。例えばABCを通る確率が0.8で、これを検証中にDをどうしても通るとしたら失敗になります。これによって探索する空間を小さくします。
実装例
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct location
{
int x;
int y;
int colors;
vector <int> trap;
};
struct probability
{
int colors;
double p;
};
struct compare
{
bool operator()(const probability &a, const probability &b)
{
return a.p > b.p;
}
};
class ColorfulMazeTwo {
private:
vector<string> map;
vector<probability> probabilityList;
int width;
int height;
bool flag[50][50];
public:
void initFlag()
{
for( int i = 0; i < 50; i++ )
for( int j = 0; j < 50; j++ )
flag[i][j] = false;
}
bool check( location &l, probability p )
{
if( l.x < 0 ) return false;
if( l.y < 0 ) return false;
if( l.x >= width ) return false;
if( l.y >= height ) return false;
if( map[l.y][l.x] == '#' ) return false;
if( flag[l.y][l.x] == true ) return false;
char floor = map[l.y][l.x];
if( 'A' <= floor && floor <= 'G' )
{
int kind = floor - 'A';
if(( p.colors & (1 << kind)) == 0 )
{
return false;
}
else
{
l.colors |= (1 << kind);
}
}
return true;
}
void calcProbability( vector<int> &trap )
{
probabilityList.clear();
probability prob;
for( int i = 0; i < 128; i++ )
{
prob.colors = i;
prob.p = 1.00;
for( int kind = 0; kind < 7; kind++ )
{
if((i & (1 << kind)) != 0 )
{
prob.p *= ( 1.00 - trap[kind] / 100.0 );
}
}
probabilityList.push_back(prob);
}
sort(probabilityList.begin(), probabilityList.end(), compare() );
}
double getProbability(vector<string> maze, vector<int> trap)
{
map = maze;
stack<location> st;
location l;
width = maze[0].length();
height = maze.size();
int start_x = 0;
int start_y = 0;
calcProbability( trap );
for( int i = 0; i < height; i++ )
{
int s = maze[i].find('$');
if( s == maze[i].npos ) continue;
start_x = s;
start_y = i;
break;
}
for( vector<probability>::iterator it = probabilityList.begin(); it != probabilityList.end(); it++ )
{
initFlag();
l.x = start_x;
l.y = start_y;
l.trap = trap;
l.colors = 0;
st.push(l);
while(!st.empty())
{
location newLocation;
l = st.top();
st.pop();
// 現在地の確認
char floor = map[l.y][l.x];
// exit
if( floor == '!' )
{
if( it->colors == l.colors )
{
return it->p;
}
else
{
continue;
}
}
for( int i = 0; i < 4; i++ )
{
newLocation = l;
newLocation.x += dx[i];
newLocation.y += dy[i];
if( check(newLocation, *it) )
{
flag[l.y][l.x] = true;
st.push(newLocation);
}
}
}
}
return 0.0;
}
};
SystemTest
81個のテストケース全てに対して通過を確認。ああ大変だった。
