ferinの競プロ帳

競プロについてのメモ

AOJ2447 A Two Floors Dungeon

問題ページ
A Two Floors Dungeon | Aizu Online Judge

解法

制約を見るとSがかなり小さい。盤面の状態の変化を全て持つと2^(50*50)で明らかに持てないがスイッチのON/OFFの全通りの2^Sであれば十分持てる。こうすると d[スイッチの状態][x座標][y座標][何階か] = (最短操作回数) として拡張dijkstraができそう。
あらかじめ2^S通りのスイッチのON/OFFについての盤面の状態を求めておく。すると、各状態で上下左右に移動できるか、階の上下ができるか、スイッチがあるかなどの判定がO(1)でできて遷移はO(1)になる。状態数O(HW2^S)なので計算量は問題なくて通る。

かなりややこしくって実装に時間がかかった…

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

int d[1<<10][55][55][2];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int w, h;
  cin >> w >> h;
  vector<string> board(h);
  REP(i, h) cin >> board[i];
  int s;
  cin >> s;
  vector<vector<string>> t(s, vector<string>(h));
  REP(i, s) REP(j, h) cin >> t[i][j];

  vector<vector<string>> ope(1<<s, vector<string>(h));

  int sx = -1, sy = -1, gx = -1, gy = -1;
  REP(y, h) REP(x, w) {
    if(board[y][x] == '%') sx = x, sy = y, board[y][x] = '_';
    if(board[y][x] == '&') gx = x, gy = y, board[y][x] = '_';
  }

  REP(i, 1<<s) {
    ope[i] = vector<string>(h, string(w, '.'));
    REP(j, s) if(i&1<<j) {
      REP(y, h) REP(x, w) {
        if(t[j][y][x] == '*') {
          if(ope[i][y][x] == '*') ope[i][y][x] = '.';
          else ope[i][y][x] = '*';
        }
      }
    }
    REP(y, h) REP(x, w) {
      if(ope[i][y][x] == '*') {
        if(board[y][x] == '_') ope[i][y][x] = '^';
        else if(board[y][x] == '^') ope[i][y][x] = '_';
        else if('a' <= board[y][x] && board[y][x] <= 'z') {
          ope[i][y][x] = board[y][x] - ('a' - 'A');
        } else if('A' <= board[y][x] && board[y][x] <= 'Z') {
          ope[i][y][x] = board[y][x] + ('a' - 'A');
        } else ope[i][y][x] = board[y][x];
      } else {
        ope[i][y][x] = board[y][x];
      }
    }
  }

  REP(i, 1<<s) REP(j, h) REP(k, w) REP(l, 2) d[i][j][k][l] = LLINF;
  d[0][sy][sx][0] = 0;
  priority_queue<VI, VVI, greater<VI>> que;
  que.push({d[0][sy][sx][0], 0, sy, sx, 0});

  while(que.size()) {
    VI v = que.top(); que.pop();
    int mask = v[1], y = v[2], x = v[3], fl = v[4];
    if(d[mask][y][x][fl] < v[0]) continue;
    // 上下左右への移動
    REP(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      char tmp[2] = {'_', '^'};
      bool cond = ope[mask][ny][nx] == tmp[fl] || (isupper(ope[mask][ny][nx]) && fl == 1) || (islower(ope[mask][ny][nx]) && fl == 0) || (ope[mask][ny][nx] == '|');
      if(IN(0LL, w, nx) && IN(0LL, h, ny) && cond
        && d[mask][ny][nx][fl] > d[mask][y][x][fl] + 1) {
        d[mask][ny][nx][fl] = d[mask][y][x][fl] + 1;
        que.push({d[mask][ny][nx][fl], mask, ny, nx, fl});
      }
    }
    // 階段
    if(ope[mask][y][x] == '|' && d[mask][y][x][!fl] > d[mask][y][x][fl] + 1) {
      d[mask][y][x][!fl] = d[mask][y][x][fl] + 1;
      que.push({d[mask][y][x][fl], mask, y, x, !fl});
    }
    // スイッチ
    if(isupper(ope[mask][y][x]) && fl == 1) {
      int nmask = mask ^ (1<<(ope[mask][y][x]-'A'));
      int nfl = fl;
      if((isupper(ope[nmask][y][x]) && islower(ope[mask][y][x]))
        || (islower(ope[nmask][y][x]) && isupper(ope[mask][y][x]))) {
        nfl = !nfl;
      }
      if(d[nmask][y][x][nfl] > d[mask][y][x][fl] + 1) {
        d[nmask][y][x][nfl] = d[mask][y][x][fl] + 1;
        que.push({d[nmask][y][x][nfl], nmask, y, x, nfl});
      }
    }
    if(islower(ope[mask][y][x]) && fl == 0) {
      int nmask = mask ^ (1<<(ope[mask][y][x]-'A'));
      int nfl = fl;
      if((isupper(ope[nmask][y][x]) && islower(ope[mask][y][x]))
        || (islower(ope[nmask][y][x]) && isupper(ope[mask][y][x]))) {
        nfl = !nfl;
      }
      if(d[nmask][y][x][nfl] > d[mask][y][x][fl] + 1) {
        d[nmask][y][x][nfl] = d[mask][y][x][fl] + 1;
        que.push({d[nmask][y][x][nfl], nmask, y, x, nfl});
      }
    }
  }

  int ret = LLINF;
  REP(i, 1<<s) REP(j, 2) chmin(ret, d[i][gy][gx][j]);
  if(ret == LLINF) cout << -1 << endl;
  else cout << ret << endl;

  return 0;
}