PKU : 2157 - Maze

問題概要

http://poj.org/problem?id=2157
入力例のようにマップが入力されます.

• S : スタート
• G : ゴール
• X : 壁
• . : 通路
• a,b,c,d,e : カギ
• A,B,C,D,E : 扉

扉は, その扉に対応するカギを全て集めてからでないと, 開けることができません.
このとき, スタートからゴールまで辿りつけるでしょうか.

アルゴリズム

A,B,C,D,Eの扉を, 開けられる扉から開けていって, ゴールまで辿りつけるかを確かめました.

プログラム

typedef pair<int,int> P;

int h,w;
int sx,sy,cnt[5];
char t[22][22];
bool hav[5],closed[22][22];

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

bool check(int x,int y){
  if(x < 0 || w <= x || y < 0 || h <= y || t[y][x] == 'X') return false;
  if(t[y][x] == 'S' || t[y][x] == 'G') return true;
  if(isupper(t[y][x])) return hav[t[y][x] - 'A'];
  return true;
}

//戻り値 : ゴールにたどり着いたかどうか
//引数に与えられた扉が開けられるなら開ける
bool bfs(int id){
  queue<P> open;
  int keyCnt = 0;
  open.push(P(sx,sy));
  memset(closed,0,sizeof(closed));

  //BFS
  while(!open.empty()){
    P p = open.front(); open.pop();
    if(closed[p.first][p.second]) continue;
    closed[p.first][p.second] = true;

    //ゴール到着
    if(t[p.second][p.first] == 'G'){
      return true;
    }
    //目当てのカギがあったら拾う
    if(t[p.second][p.first] == id + 'a'){
      keyCnt++;
    }

    rep(i,4){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];

      if(check(nx,ny)){
        open.push(P(nx,ny));
      }
    }
  }

  //カギを全て集めていたら, 扉を開けられる
  if(keyCnt == cnt[id]){
    hav[id] = true;
  }

  return false;
}

bool solve(){
  memset(hav,0,sizeof(hav));

  //開けられる扉を順番に開けていく
  rep(i,6){
    rep(j,5){
      bool flg = bfs(i);
      if(flg) return true;
    }
  }

  return false;
}

int main(void){
  while(cin>>h>>w,h||w){
    memset(cnt,0,sizeof(cnt));
    rep(i,h){
      cin>>t[i];
      rep(j,w){
        //アルファベットごとに, カギの数をカウント
        if(islower(t[i][j])){
          cnt[t[i][j]-'a']++;
        }
        if(t[i][j] == 'S'){
          sx = j;
          sy = i;
        }
      }
    }

    cout<<(solve() ? "YES" : "NO")<<endl;
  }
}