SRM 506 Div2 Hard SlimeXResidentSlime

問題

グリッドが与えられる。各セルは以下のようになっている。
#　：　壁。通過できない。
$　：　スタート地点。
1～9　：　スライムがいる地点。

あなたはグリッド上のスライムを殺して回ることが仕事である。あなたは1ターンごとに上下左右のセルに移動するものとする。
各スライムは1～9で表される特性を持っており、あなたがスライムがいるセルに踏み込んだ時、スライムは死ぬ。しかしスライムは死んでからその数字のターン後に復活する。また、死んでいるスライムがいるセルに訪れた場合はスライムは即時復活してしまう。
スタート地点からスタートしてスライムが全て死んでいる状態にできれば任務完了である。そうできるための最小ターン数を求めよ。不可能なら-1を返せ。

やりかた

まずスライムが10匹以上いると全て死んでいる状態にはどうやってもできないので-1を返す。するとスライムはせいぜい9匹以下なので、全状態を列挙して探索する事ができる。なのでまず各ゴール、スライム間の道のりを求める。その上で、スライムを訪れる順番について全順列を求めて各順列について、そのような訪れ方が可能かどうか調べ、可能なもののうち、最小のターン数のものを調べればいい。

int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};

class SlimeXResidentSlime {
public:
  int N, M;
  bool inside(int y, int x){return 0 <= y && y < N && 0 <= x && x < M;};
  int exterminate(vector <string> field) {
    map<pair<int, int>, int> num;
    int revive[11]; fill(revive, revive + 11, INF);
    int d[10][10]; 
    for(int i = 0; i < 10; i++) fill(d[i], d[i] + 10, INF);
    N = field.size(), M = field[0].length();

    //スライムが何匹以上いるか調べる
    int cnt = 0;
    for(int i = 0; i < N; i++) 
      for(int j = 0; j < M; j++)
	if(field[i][j] == '$' || isdigit(field[i][j])) cnt++;
    if(cnt > 10) return -1;

    cnt = 0;
    
    //各スライムに順番付けしていく
    for(int i = 0; i < N; i++) 
      for(int j = 0; j < M; j++) 
	if(isdigit(field[i][j])){
	  revive[cnt] = field[i][j] - '0';
	  num[make_pair(i, j)] = cnt++;
	}
    for(int i = 0; i < N; i++) 
      for(int j = 0; j < M; j++)
	if(field[i][j] == '$'){
	  revive[cnt] = INF;
	  num[make_pair(i, j)] = cnt++;
	}

    //各ゴール、スライム間の道のりを幅優先探索で求める
    map<pair<int, int>, int>::iterator it, idx;
    for(it = num.begin(); it != num.end(); it++){
      vector<vector<int> > dist(N, vector<int>(M, INF));
      dist[(it->first).first][(it->first).second] = 0;
      queue<pair<int, int> > Q;
      Q.push(it->first);
      while(!Q.empty()){
	int y = Q.front().first;
	int x = Q.front().second;
	Q.pop();
	for(int i = 0; i < 4; i++){
	  int ny = y + dy[i];
	  int nx = x + dx[i];
	  if(inside(ny, nx) && field[ny][nx] != '#' && dist[ny][nx] == INF){
	    dist[ny][nx] = dist[y][x] + 1;
	    Q.push(make_pair(ny, nx));
	  }
	}
      }
      for(idx = num.begin(); idx != num.end(); idx++)
	d[it->second][idx->second] = d[idx->second][it->second] 
	  = dist[(idx->first).first][(idx->first).second];
    }

    //各順列についてそのような訪れ方が可能か調べ、可能ならターン数の最小値を求める
    int result = INF;
    int turn[11]; for(int i = 0; i < 11; i++) turn[i] = i;
    do{
      bool ok = true;
      int path[11] = {0};
      for(int i = 1; i < cnt; i++){//訪れる順番を逆順に調べていく
	path[i] = path[i - 1] + d[turn[i]][turn[i - 1]];
	if(path[i] >= revive[turn[i]]) ok = false;
      }
      if(ok) result = min(result, path[cnt - 1]);
    }while(next_permutation(turn, turn + cnt - 1));
    //↑ゴール(cnt - 1)は必ず最後に訪れるのでnext_permutationには含めない

    return result >= INF ? -1 : result;
  }
};

もうこのあたりのグリッド中の特定のセル同士の距離をもとめるコードはスニペットとしてどこかに保存しておくことにする。