SRM 464 Div2 Hard ColorfulMazeTwo

問題

グリッド状の迷路が与えられる。各グリッドはいくつかのタイプが有り、各タイプは以下のようになっている。

'.'　通過できる
'#'　壁。通過できない
'$'　スタート地点
'!'　ゴール地点
'A ～ G'　罠の仕掛けられているグリッド　AからGまで7種類ある

スタート地点からスタートしてゴール地点に辿り着きたいとする。迷路を進んでいく際に罠のあるグリッドに踏み入れた時にゲームオーバーになってしまう確率がvector < int > trap で与えられる。もっとも生き残る確率が大きくなるように移動した時の生存確率を求めよ。ただし、一度ある種類の罠をくぐり抜ければ、同じ種類の罠のあるグリッドに入ったとしてもその罠にはかからないものとする。

やりかた

罠の種類は7種類以下のため、どの種類の罠に踏み込むかを全て列挙する。その条件をみたすようなルートが有るかを調べ、ルートが存在する場合には列挙した罠を全て回避する生存確率を計算する。すべての集合の中でこの確率の最大のものを計算すればいい。

特定の罠のみを通過するルートが有るかどうかは、その罠を通過できるグリッド'.'に置き換えて、それ以外の罠を通過できないグリッド'#'に置き換えて幅優先探索してやればよい。

以下ソース。

class ColorfulMazeTwo {
public:
  int N, M;
  bool inside(int y, int x) {return 0 <= y && y < N && 0 <= x && x < M; }
  double getProbability(vector <string> maze, vector <int> trap) {
    double result = 0.0;
    vector<string> fi;
    int sx, sy, gx, gy;

    N = maze.size(); M = maze[0].length();
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++){
	if(maze[i][j] == '$'){
	  sy = i; sx = j;
	  maze[i][j] = '.';
	}
	if(maze[i][j] == '!'){
	  gy = i; gx = j;
	  maze[i][j] = '.';
	}
      }
    
    int dy[4] = {0, -1, 0, 1};
    int dx[4] = {1, 0, -1, 0};
    //あるいくつかの罠のみを通過していくルートが有るか調べる
    //その罠の決め方を全列挙する
    for(int S = 0; S < 1 << 7; S++){
      fi = maze;
      for(int i = 0; i < N; i++)
	for(int j = 0; j < M; j++)
	  if(isalpha(fi[i][j])){
	    if(S >> (fi[i][j] - 'A') & 1)
	      fi[i][j] = '.';
	    else
	      fi[i][j] = '#';
	  }

      vector<vector<int> > d(N, vector<int>(M, INF));
      queue<int> Q;
      Q.push(sy * M + sx);
      d[sy][sx] = 0;
      while(!Q.empty()){
	int y = Q.front() / M;
	int x = Q.front() % M;
	Q.pop();
	if(y == gy && x == gx) continue;
	for(int i = 0; i < 4; i++){
	  int ny = y + dy[i];
	  int nx = x + dx[i];
	  if(inside(ny, nx) && fi[ny][nx] == '.')
	    if(d[ny][nx] > d[y][x] + 1){
	      d[ny][nx] = d[y][x] + 1;
	      Q.push(ny * M + nx);
	    }
	}
      }
      
      if(d[gy][gx] != INF){
	double p = 1.0;
	for(int i = 0; i < 7; i++)
	  if(S >> i & 1)
	    p *= (1.0 - (1.0 * trap[i] / 100));

	result = max(result, p);
      }
    }
    return result;
  }

普通のBFSではもちろんTLE