1517.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
void faceleft(vector<vector<char> > & vec,int i,int j){
    char t=vec[i][j],s=vec[i][j+1];
	vec[i][j]=vec[i][j+2];vec[i][j+2]=vec[i+2][j+2];vec[i+2][j+2]=vec[i+2][j];vec[i+2][j]=t;
	vec[i][j+1]=vec[i+1][j+2];vec[i+1][j+2]=vec[i+2][j+1];vec[i+2][j+1]=vec[i+1][j];vec[i+1][j]=s;
}
void faceright(vector<vector<char> > & vec,int i,int j){
    char t=vec[i][j],s=vec[i][j+1];
	vec[i][j]=vec[i+2][j];vec[i+2][j]=vec[i+2][j+2];vec[i+2][j+2]=vec[i][j+2];vec[i][j+2]=t;
	vec[i][j+1]=vec[i+1][j];vec[i+1][j]=vec[i+2][j+1];vec[i+2][j+1]=vec[i+1][j+2];vec[i+1][j+2]=s;
}
void cir(vector<vector<char> > & vec,int i1,int j1,int i2,int j2,int i3,int j3,int i4,int j4,int i5,int j5,int i6,int j6,int i7,int j7,int i8,int j8,int i9,int j9,int i10,int j10,int i11,int j11,int i12,int j12){
    char t=vec[i1][j1];
	vec[i1][j1]=vec[i4][j4];
	vec[i4][j4]=vec[i7][j7];
	vec[i7][j7]=vec[i10][j10];
	vec[i10][j10]=t;

    t=vec[i2][j2];
	vec[i2][j2]=vec[i5][j5];
	vec[i5][j5]=vec[i8][j8];
	vec[i8][j8]=vec[i11][j11];
	vec[i11][j11]=t;

	t=vec[i3][j3];
	vec[i3][j3]=vec[i6][j6];
	vec[i6][j6]=vec[i9][j9];
	vec[i9][j9]=vec[i12][j12];
	vec[i12][j12]=t;
}
void deal(vector<vector<char> > & vec,string s1,string s2){
    int i,j,k;
	if(s1=="front"&&s2=="left"){
        faceleft(vec,3,3);
		cir(vec,2,3,2,4,2,5,3,6,4,6,5,6,6,5,6,4,6,3,5,2,4,2,3,2);
	}
	else if(s1=="front"&&s2=="right"){
        faceright(vec,3,3);
		cir(vec,3,2,4,2,5,2,6,3,6,4,6,5,5,6,4,6,3,6,2,5,2,4,2,3);
	}
	else if(s1=="left"&&s2=="left"){
		faceleft(vec,3,0);
		cir(vec,0,3,1,3,2,3,3,3,4,3,5,3,6,3,7,3,8,3,5,11,4,11,3,11);
	}
    else if(s1=="left"&&s2=="right"){
		faceright(vec,3,0);
		cir(vec,3,11,4,11,5,11,8,3,7,3,6,3,5,3,4,3,3,3,2,3,1,3,0,3);
	}
	else if(s1=="right"&&s2=="left"){
		faceleft(vec,3,6);
		cir(vec,8,5,7,5,6,5,5,5,4,5,3,5,2,5,1,5,0,5,3,9,4,9,5,9);
	}
	else if(s1=="right"&&s2=="right"){
		faceright(vec,3,6);
		cir(vec,5,9,4,9,3,9,0,5,1,5,2,5,3,5,4,5,5,5,6,5,7,5,8,5);
	}
	else if(s1=="back"&&s2=="left"){
		faceleft(vec,3,9);
		cir(vec,0,5,0,4,0,3,3,0,4,0,5,0,8,3,8,4,8,5,5,8,4,8,3,8);
	}
	else if(s1=="back"&&s2=="right"){
		faceright(vec,3,9);
		cir(vec,3,8,4,8,5,8,8,5,8,4,8,3,5,0,4,0,3,0,0,3,0,4,0,5);
	}
	else if(s1=="top"&&s2=="left"){
		faceleft(vec,0,3);
		cir(vec,3,11,3,10,3,9,3,8,3,7,3,6,3,5,3,4,3,3,3,2,3,1,3,0);
	}
	else if(s1=="top"&&s2=="right"){
		faceright(vec,0,3);
		cir(vec,3,0,3,1,3,2,3,3,3,4,3,5,3,6,3,7,3,8,3,9,3,10,3,11);
	}
	else if(s1=="bottom"&&s2=="left"){
		faceleft(vec,6,3);
		cir(vec,5,0,5,1,5,2,5,3,5,4,5,5,5,6,5,7,5,8,5,9,5,10,5,11);
	}
	else if(s1=="bottom"&&s2=="right"){
		faceright(vec,6,3);
		cir(vec,5,11,5,10,5,9,5,8,5,7,5,6,5,5,5,4,5,3,5,2,5,1,5,0);
	}
}
int judge(vector<vector<char> > & vec){
   int flag=1,i,j;char temp;
   temp=vec[0][3];
   for(i=0;i<3;i++) for(j=3;j<6;j++) if(vec[i][j]!=temp) flag=0;
      temp=vec[3][0];
   for(i=3;i<6;i++) for(j=0;j<3;j++) if(vec[i][j]!=temp) flag=0;
      temp=vec[3][3];
   for(i=3;i<6;i++) for(j=3;j<6;j++) if(vec[i][j]!=temp) flag=0;
      temp=vec[3][6];
   for(i=3;i<6;i++) for(j=6;j<9;j++) if(vec[i][j]!=temp) flag=0;
      temp=vec[3][9];
   for(i=3;i<6;i++) for(j=9;j<12;j++) if(vec[i][j]!=temp) flag=0;
      temp=vec[6][3];
   for(i=6;i<9;i++) for(j=3;j<6;j++) if(vec[i][j]!=temp) flag=0;
   return flag;
}
int main(){
  //ifstream cin("1517.txt");
  string s;
  int i,j,n,l;
  getline(cin,s);
  istringstream cis(s);
  cis>>n;
  for(l=0;l<n;l++){
     vector<char> tep(12,' ');
	 vector<vector<char> > vec(9,tep);
	 for(i=0;i<3;i++){
		 getline(cin,s);
         istringstream is(s);
		 for(j=3;j<6;j++)
			 is>>vec[i][j];
	 }
	 for(i=3;i<6;i++){
		 getline(cin,s);
         istringstream is(s);
		 for(j=0;j<12;j++)
			 is>>vec[i][j];
	 }
     for(i=6;i<9;i++){
		 getline(cin,s);
         istringstream is(s);
		 for(j=3;j<6;j++)
			 is>>vec[i][j];
	 }
	 getline(cin,s);
	 istringstream xs(s);
	 while(xs>>i&&i!=0){
         switch (i){
		 case 1: {deal(vec,"left","right");break;}
		 case -1:{deal(vec,"left","left");break;}
		 case 2:{deal(vec,"front","right");break;}
		 case -2:{deal(vec,"front","left");break;}
		 case 3:{deal(vec,"right","right");break;}
		 case -3:{deal(vec,"right","left");break;}
		 case 4:{deal(vec,"back","right");break;}
		 case -4:{deal(vec,"back","left");break;}
		 case 5:{deal(vec,"top","right");break;}
		 case -5:{deal(vec,"top","left");break;}
		 case 6:{deal(vec,"bottom","right");break;}
		 case -6:{deal(vec,"bottom","left");break;}
		 }
	 }
	 if(judge(vec)) cout<<"Yes, grandpa!\n";
	 else cout<<"No, you are wrong!\n";
/*	 for(i=0;i<9;i++){
		 for(j=0;j<12;j++)
			 cout<<vec[i][j];
		 cout<<endl;
	 }*/
  }
}