AOJ 0172 : Doctor's Research Rooms

問題リンク:Doctor's Research Rooms | Aizu Online Judge

問題概要：
n個の部屋がある
ゴール以外の部屋の明かりを全て消してゴールまで到達できるか？
できるなら最小のステップ数とそのステップを出力せよ
ゴール以外の部屋全ての明かりを消すことができないなら　You can not switch off all lights.　と出力、　そもそもゴールに到達できないなら Help me! と出力せよ

使用した言語：C++

解法：
bitとステップを持たせてbfsした。bitには各部屋の明かりの状態を保存し、vectorには何をしたかをintに置き換えて保存した。

最小コストには int mincost という配列を用意し、
mincost[各部屋の明かりの状態][今いる部屋] =　この部屋の明かりの状態でこの部屋にくるための最小コスト　とした
bitがたっていれば明かりがついているものとした
それまでに行ったステップはvectorにpairでつめた
firstの要素が 1 なら Move, 2 なら Switch off, 3 なら Switch onとした

コード：

#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cassert>
#include<algorithm>
#include<bitset>
#include<deque>
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
struct Pox
{
  int cost;
  int p;
  int bit;
  vector<P> step;
  // P(1,R) -> Move to room R.
  // P(2,R) -> Switch off room R.
  // P(3,R) -> Switch on room R.

  Pox(int p,int bit,int cost):p(p),bit(bit),cost(cost){step.clear();}
};

int n,m;

int main()
{
  while(cin >> n >> m, (n || m))
    {
      VVI G;
      G.resize(n);
      for(int i=0;i<m;i++)
	{
	  int s,t;
	  scanf("%d %d",&s,&t);
	  t--,s--;
	  G[s].push_back(t);
	  G[t].push_back(s);
	}
      int initial_bit = 0;
      for(int i=0;i<n;i++)
	{
	  int b;
	  cin >> b;
	  if(b)
	    initial_bit |= (1<<i);
	}
   
      VVI E;
      E.resize(n);
      for(int i=0;i<n;i++)
	{
	  int k;
	  cin >> k;
	  for(int j=0;j<k;j++)
	    {
	      int r;
	      cin >> r;
	      r--;
	      E[i].push_back(r);
	    }
	  sort(E[i].begin(),E[i].end());
	}

      int mincost[1<<n][n];
      for(int i=0;i<=(1<<n)-1;i++)
	for(int j=0;j<n;j++)
	  mincost[i][j] = (1<<29);

      deque<Pox> deq;
      mincost[initial_bit][0] = 0;
      deq.push_back(Pox(0,initial_bit,0));

      int men_cost = (1<<29);
      vector<P> men_step;
      bool sub = false;

      while(!deq.empty())
	{
	  Pox pox = deq.front(); deq.pop_front();
	  
	  if(!((pox.bit >> pox.p) & 1))
	    continue;

	  if(pox.p == n-1 && __builtin_popcount(pox.bit) == 1 && (pox.bit>>(n-1)) & 1) 
	    {
	      if(men_cost > pox.cost)
		{
		  men_cost = pox.cost;
		  men_step = pox.step;
		}
	    }
	  else if(pox.p == n-1)
	    {
	      sub = true;
	    }

	  for(int i=0;i<G[pox.p].size();i++)
	    {// Move
	      int next = G[pox.p][i];

	      if(!((pox.bit>>next)&1))
		continue;

	      if(mincost[pox.bit][next] > pox.cost + 1)
		{
		  mincost[pox.bit][next] = pox.cost + 1;
		  Pox next_pox = Pox(next,pox.bit,pox.cost+1);
		  next_pox.step = pox.step;
		  next_pox.step.push_back(P(1,next));
		  deq.push_back(next_pox);
		}
	    }// Move

	  for(int i=0;i<E[pox.p].size();i++)
	    {
	      int next = E[pox.p][i];
	      
	      if(next == pox.p)
		continue;

	      bool swit = (pox.bit>>next)&1?0:1;
	      int nbit;
	      if(swit)
		  nbit = pox.bit,nbit |= (1<<next);
	      else 
		  nbit = pox.bit, nbit &= ~(1<<next);

	      bitset<10> before(nbit);

	      if(mincost[nbit][pox.p] > pox.cost+1)
		{
   		  mincost[nbit][pox.p] = pox.cost + 1;
		  Pox next_pox = Pox(pox.p,nbit,pox.cost+1);
		  next_pox.step = pox.step;
		  next_pox.step.push_back(P(swit?3:2,next));
		  deq.push_back(next_pox);
		}
	    }
	}

      if(men_cost == (1<<29) && !sub)
	  cout << "Help me!" << endl;
      else if(men_cost == (1<<29) && sub)
	  cout << "You can not switch off all lights." << endl;
      else if(men_cost != (1<<29))
	{
	  cout << "You can go home in " << men_cost << " steps." << endl;
	  for(int i=0;i<men_step.size();i++)
	    {
	      P p = men_step[i];
	      if(p.F == 1)
		cout << "Move to room " << p.S+1 << "." << endl;
	      else if(p.F == 2)
		cout << "Switch off room " << p.S+1 << "." << endl;
	      else if(p.F == 3)
		cout << "Switch on room " << p.S+1 << "." << endl;
	      else
		assert(false);
	    }
	}
    }
  return 0;
}