AOJ : 2089 - Mysterious Dungeons

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2089
小文字のアルファベットを踏むと, そのアルファベットの大文字にあたる場所が歩ける場所に変化.
さらに踏むと, 岩に変化 -> さらに踏むと, 歩ける場所に変化 -> ...

このとき, スタート地点('@') からゴール地点('<') まで, 最小歩数がいくらかを求める問題です.
もし, そのような解がなければ -1 を出力します.

アルゴリズム

次の状態を持つクラスを作って, ダイクストラで解きました.

• 現在の x 座標
• 現在の y 座標
• 現在の歩数
• 大文字のアルファベットの位置の中で歩ける場所 (ビット管理)

解説見ると, 幅優先で十分だったって!
あはは.
そんなにコードの長さ変わらないだろうから別にいいや.

プログラム

#include <iostream>
#include <queue>
#include <cstring>
#include <map>
using namespace std;

class P{
public:
  int x,y,cost,bit;

  P(int _x,int _y,int _cost,int _bit){
    x = _x;
    y = _y;
    cost = _cost;
    bit = _bit;
  }

  bool operator<(const P &p)const{
    return cost > p.cost;
  }
};

int w,h;
int s[32][32];
char t[32][32];

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

int solve(int sx,int sy){
  priority_queue<P> open;
  map< int, map<int, map<int, bool> > > closed;

  open.push(P(sx,sy,0,0));

  while(!open.empty()){
    P p = open.top(); open.pop();

    if(closed[p.x][p.y][p.bit]) continue;
    closed[p.x][p.y][p.bit] = true;

    if(t[p.y][p.x] == '<'){
      return p.cost;
    }

    for(int i=0;i<4;i++){
      int nx = p.x + dx[i];
      int ny = p.y + dy[i];

      if(t[ny][nx]=='#') continue;

      //小文字 ... 岩状態のbit反転
      if(s[ny][nx] < 0){
        open.push(P(nx,ny,p.cost+1,(p.bit ^ (1<<(-s[ny][nx])))));
      }
      //大文字
      else if(s[ny][nx] > 0){
        if( (p.bit & (1<<s[ny][nx])) != 0 ){
          open.push(P(nx,ny,p.cost+1,p.bit));
        }
      }
      else{
        open.push(P(nx,ny,p.cost+1,p.bit));
      }
    }
  }

  return -1;
}

int main(void){
  while(cin>>w>>h && (w||h)){
    int sx,sy;
    int alpha[26],size=1;
    memset(alpha,-1,sizeof(alpha));
    memset(s,0,sizeof(s));

    for(int i=0;i<h;i++){
      cin>>t[i];
      for(int j=0;j<w;j++){
        if('A' <= t[i][j] && t[i][j] <= 'Z'){
          int idx = t[i][j] - 'A';
          if(alpha[idx] == -1){
            alpha[idx] = size++;
          }
          t[i][j] = '.';
          s[i][j] = alpha[idx];
        }
        else if('a' <= t[i][j] && t[i][j] <= 'z'){
          int idx = t[i][j] - 'a';
          if(alpha[idx] == -1){
            alpha[idx] = size++;
          }
          t[i][j] = '.';
          s[i][j] = -alpha[idx];
        }
        else if(t[i][j] == '@'){
          sx = j;
          sy = i;
        }
      }
    }

    cout<<solve(sx,sy)<<endl;
  }

  return 0;
}