AOJ2447 A Two Floors Dungeon

問題リンク
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2447

解法

1,2階の状態を一つのグリッドで表現するのでかなり分かりにくいが, 整理するとマスの位置, 今いるフロアの階数, スイッチの状態をもってBFSをすればよいことが分かる.
少し面倒なのが移動可能かどうかの判定だがどのスイッチが押されているとき変更されるかをあらかじめビットで持っておくとスイッチの状態とのAND演算をとるだけでよくなる. ^及び'A'~'J'ははじめ二階にあることに注意する.

実装例

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;


#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()

#define MOD 1000000007

template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
const double EPS = 1e-9, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;

int dp[55][55][2][1<<10];
int dxy[5]={-1,0,1,0,-1};
int mask[55][55];
vector<string> M(55);
bool canmove(int y, int x, int floor, int swi) {

  if(M[y][x] == '|') return true;
  int carry = 0;
  if((M[y][x] >= 'A' && M[y][x] <= 'J')||(M[y][x] == '^')) carry = 1;
  int mask2 = mask[y][x] & swi;
  carry = (carry + __builtin_popcount(mask2)) % 2;
  return floor == carry;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(7);
  
  int W, H; cin >> W >> H;
  
  REP(i,H) cin >> M[i];

  int S; cin >> S;
  REP(i,H) REP(j,W) REP(k,2) REP(l,(1<<S)) dp[i][j][k][l] = INT_MAX;
  
  
  REP(i,S) {
    REP(j,H) {
      string s; cin >> s;
      REP(k,W) {
        if(s[k] == '*') {
          mask[j][k] |= (1 << i);
        }
      }
    }
  }

  int sy, sx, gy, gx;
  REP(i,H) {
    REP(j,W) {
      if(M[i][j] == '%') {
        sy = i, sx = j;
      }
      if(M[i][j] == '&') {
        gy = i, gx = j;
      }
    }
  }
  dp[sy][sx][0][0] = 0;
  queue<tuple<int, int, int, int>> q;
  q.push(make_tuple(sy, sx, 0, 0));
  while(q.size()) {
    auto[y, x, floor, swi] = q.front();
    q.pop();

    if(M[y][x] == '|') {
      if(dp[y][x][floor^1][swi] > dp[y][x][floor][swi] + 1) {
        dp[y][x][floor^1][swi] = dp[y][x][floor][swi] + 1;
        q.push(make_tuple(y,x,floor^1,swi));
      }
    }else if(M[y][x] >= 'A' && M[y][x] <= 'J') {
      int tmp = 0;
      if(mask[y][x] & (1 << (M[y][x]-'A'))) tmp = 1;

      if((swi >> (M[y][x]-'A')) & 1) {
        if(dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'A'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'A'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi & ~(1 << (M[y][x]-'A'))));
        }
      }else{
        if(dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'A'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'A'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi | (1 << (M[y][x]-'A'))));
        }
      }
    }else if(M[y][x] >= 'a' && M[y][x] <= 'j') {
      int tmp = 0;
      if(mask[y][x] & (1 << (M[y][x]-'a'))) tmp = 1;

      if((swi >> (M[y][x]-'a')) & 1) {
        if(dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'a'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi & ~(1 << (M[y][x]-'a'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi & ~(1 << (M[y][x]-'a'))));
        }
      }else{
        if(dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'a'))] > dp[y][x][floor][swi] + 1) {
          dp[y][x][floor^tmp][swi | (1 << (M[y][x]-'a'))] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(y,x,floor^tmp,swi | (1 << (M[y][x]-'a'))));
        }
      }
    }
    
    for(int i=0; i<4; i++) {
      int ny = y + dxy[i], nx = x + dxy[i+1];
      if(M[ny][nx] != '#' && canmove(ny, nx, floor, swi)) {
        if(dp[ny][nx][floor][swi] > dp[y][x][floor][swi] + 1) {
          dp[ny][nx][floor][swi] = dp[y][x][floor][swi] + 1;
          q.push(make_tuple(ny,nx,floor,swi));
        }
      }
    }
  }

  int ans = INT_MAX;
  REP(i,2) {
    REP(j,(1<<S)) {
      ans = min(ans, dp[gy][gx][i][j]);
    }
  }
  if(ans == INT_MAX) ans = -1;
  cout << ans << endl;
  return 0;
}