1301.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<string>
#include<vector>
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
const string mov1="- Move to room ";
const string mov2=".\n";
const string off="- Switch off light in room ";
const string on="- Switch on light in room ";
class item{
public:
	int local,index;
	vector<int> light;
	string path;
	item(){}
	item(int r){light.resize(r,0);local=0;light[0]=1;path="";}
	item(const item & s){light=s.light;local=s.local;path=s.path;}
    void init(int r){
       index=0;int i;
	   for(i=0;i<r;i++){
          index+=light[i]*pow(2,i);
	   }
	   index+=local*pow(2,r);
	}
};
int main(){
    //ifstream cin("in.txt");
	int i,j,k,r,d,l,c=1,aim;
    while(cin>>r>>d>>l&&!(r==0&&d==0&&l==0)){
	    cout<<"Villa #"<<c++<<endl;
        vector<int> cmp(r*pow(2,r),0);
		vector<vector<int> > vecd(r),vecl(r);
		item aimitem(r);
        aimitem.local=r-1;
		aimitem.light[0]=0;
		aimitem.light.back()=1;
		aimitem.init(r);
		aim=aimitem.index;
		//cout<<aim<<endl;
		for(i=0;i<d;i++){
           cin>>j>>k;
		   vecd[j-1].push_back(k-1);
		   vecd[k-1].push_back(j-1);
		}
		for(i=0;i<l;i++){
           cin>>j>>k;
		   vecl[j-1].push_back(k-1);
		}
		if(r==1) {cout<<"The problem can be solved in 0 steps:\n\n"; continue;}
		item begin(r); begin.init(r); cmp[begin.index]=1;
        vector<item> last,now; last.push_back(begin);
		d=0;
		while(last.size()){
			d+=1;
            for(i=0;i<last.size();i++){
				for(j=0;j<vecd[last[i].local].size();j++){
                    k=vecd[last[i].local][j];
					if(last[i].light[k]==1){
                        item temp(last[i]);
						temp.local=k;
						temp.init(r);
						if(cmp[temp.index]==0){
                            cmp[temp.index]=1;
					        temp.path.insert(temp.path.end(),mov1.begin(),mov1.end());
							if(k<=8) temp.path.insert(temp.path.end(),char('1'+k));
							else{
                                temp.path.insert(temp.path.end(),'1');
								temp.path.insert(temp.path.end(),'0');
							}
							temp.path.insert(temp.path.end(),mov2.begin(),mov2.end());
							now.push_back(temp);
							if(temp.index==aim){cout<<"The problem can be solved in "<<d<<" steps:\n"<<temp.path; goto outer;}
						}
					}
				}
				for(j=0;j<vecl[last[i].local].size();j++){
                    k=vecl[last[i].local][j];
					if(k!=last[i].local){
                        item temp(last[i]);
						if(temp.light[k]==1) {temp.light[k]=0;l=0;}
						else {temp.light[k]=1;l=1;}
						temp.init(r);
						if(cmp[temp.index]==0){
							cmp[temp.index]=1;
							if(l==1) temp.path.insert(temp.path.end(),on.begin(),on.end());
							else temp.path.insert(temp.path.end(),off.begin(),off.end());
							if(k<=8) temp.path.insert(temp.path.end(),char('1'+k));
							else{
                                temp.path.insert(temp.path.end(),'1');
								temp.path.insert(temp.path.end(),'0');
							}
							temp.path.insert(temp.path.end(),mov2.begin(),mov2.end());
							now.push_back(temp);
							if(temp.index==aim){cout<<"The problem can be solved in "<<d<<" steps:\n"<<temp.path; goto outer;}
						}
					}
				}
			}
			last=now; now.clear();
		}
		cout<<"The problem cannot be solved.\n";
        outer:
		cout<<endl;
	}
	return 0;
}