AOJ : 0172 - Doctor's Research Rooms

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0172&lang=jp
日本語の問題文なので, 説明は省略します.

アルゴリズム

次の４変数を状態としてもたせて, 幅優先しました.

• 現在の部屋番号
• 現在どの部屋の明かりがついているか(ビット管理)
• ステップ数
• 今までに行った動作(vector管理)

動作は３種類ありますが, 各動作を次のようにint型ひとつで識別できるようにしました.

• 1以上, 100未満の正整数 : この番号の明かりをつけた
• 0未満の整数 : (この番号 * (-1)) の明かりを消した
• 101以上の正整数 : (この番号 - 100) の部屋に移動した

注意点

• 次状態に遷移するとき, 自分の部屋の明かりを消してはいけない

プログラム

int n,m;
bool t[16][16],closed[16][66000];
vector<int> r[16];

class P{
public:
  int id,bit,cost;
  vector<int> pass;

  P(){}
  P(int _id,int _bit,int _cost,vector<int> _pass){
    id = _id;
    bit = _bit;
    cost = _cost;
    pass = _pass;
  }
};

void printPass(vector<int> v){
  cout<<"You can go home in "<<v.size()<<" steps.\n";
  for(int i=0;i<v.size();i++){
    if(v[i] >= 100)
      cout<<"Move to room "<<v[i]/100<<".\n";
    else if(v[i] > 0)
      cout<<"Switch on room "<<v[i]<<".\n";
    else
      cout<<"Switch off room "<<-v[i]<<".\n";
  }
}

int main(void){
  while(cin>>n>>m,n){
    memset(t,0,sizeof(t));
    for(int i=0;i<m;i++){
      int a,b;
      cin>>a>>b;
      a--; b--;
      t[a][b] = t[b][a] = true;
    }
    int first = 0;
    for(int i=0;i<n;i++){
      int x;
      cin>>x;
      if(x) first |= (1<<i);
    }
    for(int i=0;i<n;i++){
      int k;
      cin>>k;
      r[i].clear();

      while(k--){
        int ri;
        cin>>ri;
        ri--;
        r[i].push_back(ri);
      }

      sort(r[i].begin(),r[i].end());
    }

    queue<P> open;
    memset(closed,0,sizeof(closed));
    open.push(P(0,first,0,vector<int>()));

    int ansCode = 0;
    P ans;
    while(!open.empty()){
      P p = open.front(); open.pop();
      if(closed[p.id][p.bit]) continue;
      closed[p.id][p.bit] = true;

      if(p.id == n-1){
        if(p.bit == (1<<(n-1))){
          ansCode = 2;
          ans = p;
          break;
        }
        ansCode = 1;
      }

      for(int i=0;i<r[p.id].size();i++){
        if(r[p.id][i] == p.id) continue;

        int now = (p.bit & (1<<r[p.id][i]));
        int nbit = (p.bit ^ (1<<r[p.id][i]));
        vector<int> npass = p.pass;

        if(now > 0){ //switch off
          npass.push_back(-r[p.id][i]-1);
        }
        else{
          npass.push_back(r[p.id][i]+1);
        }
        open.push(P(p.id,nbit,p.cost+1,npass));
      }

      for(int i=0;i<n;i++){
        if(t[p.id][i] && (p.bit & (1<<i))>0){
          vector<int> npass = p.pass;
          npass.push_back((i+1)*100);
          open.push(P(i,p.bit,p.cost+1,npass));
        }
      }
    }

    if(ansCode == 2)
      printPass(ans.pass);
    else if(ansCode == 1)
      cout<<"You can not switch off all lights.\n";
    else
      cout<<"Help me!\n";
  }

  return 0;
}