1332.cpp

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

#include<vector>
#include<fstream>
#include<iostream>
using namespace std;
void set(vector<vector<int> > & o,vector<vector<int> > & map,int i,int j,int w,int h){
     for(int ii=0;ii<h;ii++)
		 for(int jj=0;jj<w;jj++)
			 if(o[ii][jj]!=0)
			 map[i+ii][j+jj]=o[ii][jj];
}
bool canset(vector<vector<int> > & o,vector<vector<int> > & map,int i,int j,int w,int h){
   if(i+h>4||j+w>4) return false;
   else{
     for(int ii=0;ii<h;ii++)
		 for(int jj=0;jj<w;jj++)
			 if(map[i+ii][j+jj]*o[ii][jj]!=0) return false;
	 return true;
   }
}
void deal(vector<vector<vector<int> > > & vec,vector<vector<int> > & omap,vector<vector<int> > map,int d,int & flag){
    if(d==vec.size()){flag=1;omap=map;return;}
	else{
        int w=vec[d][0].size(),h=vec[d].size();
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)
			   if(!flag&&canset(vec[d],map,i,j,w,h)){
			       vector<vector<int> > copymap=map;
				   set(vec[d],map,i,j,w,h);
				   d+=1;
				   deal(vec,omap,map,d,flag);
				   d-=1;
				   map=copymap;
			   }
	}
}
int main(){
  //ifstream cin("1332.txt");
  int n,i,j,k,a,b,t,bl=0;
  char c;
  while(cin>>n&&n){
	 if(bl) cout<<endl;
	 bl=1;
     vector<vector<vector<int> > > vec;
	 for(k=1;k<=n;k++){
         cin>>a>>b;
		 vector<int> temp(b,0);
		 vector<vector<int> > aaa(a,temp);
		 for(i=0;i<a;i++)
			 for(j=0;j<b;j++){
                cin>>c;
				if(c=='1') aaa[i][j]=k;
			 }
		 vec.push_back(aaa);
	 }
	 t=0;
	 vector<int> zzz(4,0);
	 vector<vector<int> > map(4,zzz),omap=map;
     deal(vec,omap,map,0,t);
	 if(t){
		 for(i=0;i<4;i++)
            for(j=0;j<4;j++)
				if(omap[i][j]==0) t=0;
	 }
	 if(!t) cout<<"No solution possible\n";
	 else{
		 for(i=0;i<4;i++){
            for(j=0;j<4;j++)
				cout<<omap[i][j];
			cout<<endl;
		 }
	 }
  }
}