2011/10/31(Mon) 10:54:23 編集(投稿者)
やってみたら小手先のテクニックで解決できました。
解法
部屋数が少ないために一見計算量が小さく見えますが、部屋の明かりの状態が2＾部屋数乗通りあるために見た眼よりも計算量が多い問題です。
意外と組み合わせ数が多くグラフに翻訳しても頂点数が「部屋の数*明りの状態＾部屋数」ということになりグラフでも簡単には解けません。
また正解ルートを保持する必要があるためメモリ使用量制限３２MB（個の問題は32Mb以上メモリを使ってはいけない）にも引っかかることになります。
このためグラフの手法も幅優先探索も使えません。
そこで手順数が最小になる手順になるルールに従ってのみ移動するという深さ優先探索の手法が有効になります。
解法は以下のとおりとなります。
部屋から部屋へ移動する操作を深さ優先探索で求めます。
移動中あった部屋のスイッチをON、Offできるスイッチとして覚えておきます。
探索中は今まで入った部屋にあったスイッチを全て覚えておきます。
これはスイッチをONOFFにできる部屋として記憶します。
移動中さかのぼってONOFF出来る部屋に入ったとします。
するとその部屋のスイッチは過去において消してはいけないので、消すことが出来ないスイッチなのでOnOff履歴からはずします。
もし真っ暗な部屋に入ったら、過去の部屋にさかのぼってその部屋のスイッチを入れていたことにして先に進みます。
後はこれを深さ優先探索として実装します。
//練習問題であるためいくつかの変数名を縮めています。
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
struct switchMemo{
//ある部屋で操作したスウィッチの記録
char onOf;
int roomNo,turn;
bool operator<(const switchMemo& s)const{
return roomNo<s.roomNo;
}
};
struct rootMemo{
int turn,lightState,nowRoomNo,lightOffMemo;//
//通ってきた部屋順と操作したスウィッチを記録する
std::vector<std::set<switchMemo> > switchsMemo;
std::vector<int> root;
};
struct stateMemo{
//同じ部屋で同じライトの状態でないかを記録し無限ループを防ぐ
int nowRoomNo,lightState,lightOffMemo,turn;//roomsMemo;
bool operator<(const stateMemo& sm)const{
if(nowRoomNo!=sm.nowRoomNo)return nowRoomNo<sm.nowRoomNo;
//if(roomsMemo!=sm.roomsMemo)return roomsMemo<sm.roomsMemo;
if(lightOffMemo!=sm.lightOffMemo)return lightOffMemo<sm.lightOffMemo;
return lightState<sm.lightState;
}
void set(rootMemo& nowRoot){
nowRoomNo=nowRoot.nowRoomNo;
lightState=nowRoot.lightState;
//roomsMemo=nowRoot.roomsMemo;
lightOffMemo=nowRoot.lightOffMemo;
turn=nowRoot.turn;
}
};
//グローバル変数はここに集める
const int roomSize=16;
const char SwitchOn='n',SwitchOff='f',RoomMove='m';
std::set<switchMemo> dsets;
int n,m;
bool goalOK=false,allOfOK=false;
rootMemo ansRoot;
//ここまで
void print(rootMemo& ansRoot){
std::set<switchMemo>::iterator it;
printf("You can go home in %d steps.\n",ansRoot.turn);
for(unsigned int i=0;i<ansRoot.root.size();i++){
if(i!=0){
printf("Move to room %d.\n",ansRoot.root[i]);
}
it=ansRoot.switchsMemo[i].begin();
while(it!=ansRoot.switchsMemo[i].end()){
if((*it).onOf==SwitchOn){
printf("Switch on room %d.\n",(*it).roomNo);
}else{
printf("Switch off room %d.\n",(*it).roomNo);
}
it++;
}
}
}
bool backSwitchOn(rootMemo& rm,std::vector<int> roomSwitchs[roomSize],switchMemo& bs){
unsigned int t1;
int nowRoomNo=rm.nowRoomNo;
//ある部屋に入った時その部屋が真っ暗なら過去にさかのぼってスイッチのあった部屋でスイッチを入れてたことにする。
//スイッチが見つからず部屋に入ることが不可能ならfalseを返す
switchMemo sm;
bs.roomNo=sm.roomNo=nowRoomNo;
bs.onOf=sm.onOf=SwitchOn;
for(int i=0;i<rm.root.size()-1;i++){
t1=roomSwitchs[rm.root[i]].size();
for(int j=0;j<t1;j++){
if(nowRoomNo==roomSwitchs[rm.root[i]][j]){
rm.lightState|=(1<<(nowRoomNo-1));
rm.switchsMemo[i].insert(sm);
rm.turn++;
bs.turn=i;
return true;
}
}
}
return false;
}
bool backSwitchAllOf(rootMemo rm,std::vector<int> roomSwitchs[roomSize]){
int lightState=rm.lightState,nowRoom,nowSwitchBit,nowSwitch;
//最後の部屋に入った時過去にさかのぼり消しても問題のない部屋を全て消していたことにする。
switchMemo sm;
sm.onOf=SwitchOff;
bool onOfOK[roomSize];
memset(onOfOK,true,roomSize);
std::set<switchMemo>::iterator it;
for(int i=rm.root.size()-1;i>=0;i--){
nowRoom=rm.root[i];
onOfOK[nowRoom]=false;
for(unsigned int j=0;j<roomSwitchs[nowRoom].size();j++){
nowSwitch=roomSwitchs[nowRoom][j];
nowSwitchBit=(1<<(nowSwitch-1));
if((lightState&nowSwitchBit)!=0 && onOfOK[nowSwitch]==true){
lightState=(lightState&(~nowSwitchBit));
sm.roomNo=nowSwitch;
rm.switchsMemo[i].insert(sm);
rm.turn++;
}
}
}
if(lightState==(1<<(n-1))){
if(ansRoot.turn>rm.turn){
ansRoot=rm;
allOfOK=true;
}
return true;
}
return false;
}
void remove(rootMemo& nowRoot,switchMemo& backOnSwitch,stateMemo& backState){
//この探索ルートは失敗なので元に戻す
nowRoot.root.pop_back();
nowRoot.nowRoomNo =backState.nowRoomNo;
nowRoot.lightState =backState.lightState;
nowRoot.lightOffMemo =backState.lightOffMemo;
nowRoot.turn =backState.turn;
//スイッチを操作したが、過去と同じ状態になった
if(backOnSwitch.turn!=-1){
nowRoot.switchsMemo[backOnSwitch.turn].erase(backOnSwitch);
}
}
void rootSearch(rootMemo& nowRoot,int nextRoom,
bool roomConnect[roomSize][roomSize],std::vector<int> roomSwitchs[roomSize],std::set<stateMemo>& statesMemo);
if(ansRoot.turn<=nowRoot.turn) return;
if(nowRoot.nowRoomNo==n){
int offs=nowRoot.lightOffMemo|(1<<(n-1));
if((nowRoot.lightState&offs)==nowRoot.lightState && backSwitchAllOf(nowRoot,roomSwitchs)==true){
}else{
goalOK=true;
}
}
stateMemo nowState,backState;
switchMemo backSwitch;//もし駄目だった場合元に戻す
backSwitch.turn=-1;
backState.set(nowRoot);//失敗した場合元に戻すための記録
nowRoot.nowRoomNo=nextRoom;
nowRoot.root.push_back(nowRoot.nowRoomNo);
while(nowRoot.root.size()>nowRoot.switchsMemo.size()){
nowRoot.switchsMemo.push_back(dsets);
}
if((nowRoot.lightState&(1<<(nowRoot.nowRoomNo-1)))!=0){
//明るい部屋にそのまま移動
}else if(backSwitchOn(nowRoot,roomSwitchs,backSwitch)){
//もし部屋が暗かったら過去に辿った部屋でスイッチをつけていたことにして移動する
}else{
remove(nowRoot,backSwitch,backState);
return ;
}
nowRoot.turn++;//移動したのでターン数を増やす
for(unsigned int i=0;i<roomSwitchs[nowRoot.nowRoomNo].size();i++){
nowRoot.lightOffMemo|=(1<<(roomSwitchs[nowRoot.nowRoomNo][i]-1));//消せるスイッチのリスト
}
nowRoot.lightOffMemo&=(~(1<<(nowRoot.nowRoomNo-1))); //今いる部屋は消せないので元に戻す
nowState.set(nowRoot);
if(statesMemo.find(nowState)==statesMemo.end()){
statesMemo.insert(nowState);
}else{
int tTurn=(*statesMemo.find(nowState)).turn ;
if(tTurn>nowState.turn){
statesMemo.erase(nowState);
statesMemo.insert(nowState);
}else{
remove(nowRoot,backSwitch,backState);
return;
}
}
for(int i=1;i<=n;i++){
if(roomConnect[nextRoom][i]){
rootSearch(nowRoot,i,roomConnect,roomSwitchs,statesMemo);
}
}
remove(nowRoot,backSwitch,backState);
}
void setData(){
int p1,p2,roomLightState;//1bitずつ管理;
bool roomConnect[roomSize][roomSize];
std::vector<int> roomSwitchs[roomSize];
memset(roomConnect,false,roomSize*roomSize);
for(int i=0;i<m;i++){
scanf("%d %d",&p1,&p2);
roomConnect[p1][p2]=roomConnect[p2][p1]=true;
}
roomLightState=0;//ライトのオンオフ管理
for(int i=1;i<=n;i++){
scanf("%d",&p1);
roomLightState|=p1==0?0:1<<(i-1);
}
int s,t;
for(int i=1;i<=n;i++){
scanf("%d",&s);
for(int j=0;j<s;j++){
scanf("%d",&t);
if(i!=t){
roomSwitchs[i].push_back(t);
}
}
}
//データの読み込み終わり
//ここから深さ優先探索で部屋の移動をシミュレートするための初期データセット
std::set<stateMemo> statesMemo;
stateMemo nowState;
rootMemo nowRoot,tempRoot;
nowRoot.nowRoomNo=1;
nowRoot.lightState=roomLightState;
nowRoot.turn=-1;
nowRoot.lightOffMemo=0;
ansRoot.turn=1000000000;
int nowRoomNo;
goalOK=allOfOK=false;
//深さ優先探索
rootSearch(nowRoot,1,roomConnect,roomSwitchs,statesMemo);
if(allOfOK==true){
print(ansRoot);
}else if(goalOK==true){
printf("You can not switch off all lights.\n");
}else{
printf("Help me!\n");
}
}
int main(){
while(1){
scanf("%d %d",&n,&m);
if(n==0 && m==0)break;
setData();
}
}