1281.cpp

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

#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
int p[4][2]={1,0,0,1,-1,0,0,-1};
void cov(int & i,int & j,int & k){
    if(k>=1&&k<=3) {i=0; j=k+1; return;}
	else if(k>=4&&k<=6) {i=1; j=k-2; return;}
	else if(k>=7&&k<=13){i=2; j=k-7; return;}
	else if(k>=14&&k<=20){i=3;j=k-14;return;}
	else if(k>=21&&k<=27){i=4;j=k-21;return;}
	else if(k>=28&&k<=30){i=5;j=k-26;return;}
	else {i=6;j=k-29;return;}
}
bool hefa(int i,int j){
    if((i==0||i==1)&&(j<=4&&j>=2)) return 1;
	if((i<=4&&i>=2)&&(j>=0&&j<=6)) return 1;
	if((i==5||i==6)&&(j<=4&&j>=2)) return 1;
	return 0;
}
bool can(int i,int j,vector<vector<char> > & vec,int k){
    int i1,i2,j1,j2;
	i1=i+p[k][0];i2=i+2*p[k][0];
	j1=j+p[k][1];j2=j+2*p[k][1];
	if(!hefa(i1,j1)) return 0;
    if(!hefa(i2,j2)) return 0;
	if(vec[i1][j1]=='X'&&vec[i2][j2]=='O') return 1;
	return 0;
}
int covback(int i,int j){
    if(i==0) return j-1;
	if(i==1) return j+2;
	if(i==2) return j+7;
	if(i==3) return j+14;
	if(i==4) return j+21;
	if(i==5) return j+26;
	if(i==6) return j+29;
}
int main(){
   //ifstream cin("in.txt");
   int i,j,loop,n,k,l,s,f,ii,jj,kk,debug;
   cout<<"HI Q OUTPUT\n";
   cin>>l;
   for(loop=0;loop<l;loop++){
      vector<char> vectmp(7,'O');
	  vector<vector<char> > vec(7,vectmp);
	  while(cin>>k&&k){
          cov(i,j,k);
		  vec[i][j]='X';
	  }
	  f=1;s=0;
	  while(f){
	  f=0;ii=-1;jj=-1;
      for(i=0;i<7;i++)
		  for(j=0;j<7;j++)
			  if(vec[i][j]=='X')
                  for(n=0;n<4;n++)
					  if(can(i,j,vec,n)){
						  if(ii==-1||i+2*p[n][0]>ii+2*p[kk][0]||(i+2*p[n][0]==ii+2*p[kk][0]&&j+2*p[n][1]>=jj+2*p[kk][1])){
                              f=1;ii=i;jj=j;kk=n;
						  }
					  }
	  if(f){
	  int i1,i2,j1,j2;
	  i1=ii+p[kk][0];i2=ii+2*p[kk][0];
	  j1=jj+p[kk][1];j2=jj+2*p[kk][1];
	  vec[i1][j1]='O';vec[ii][jj]='O';vec[i2][j2]='X';
	  }
	  /*
	  for(i=0;i<7;i++){
         for(j=0;j<7;j++)
			 cout<<vec[i][j]<<" ";
		 cout<<endl;
	  }
	  cout<<endl;
	  cin>>debug;*/
	  }

	  for(i=0;i<7;i++)
		  for(j=0;j<7;j++)
			  if(vec[i][j]=='X')
				  s+=covback(i,j);
	  cout<<s<<endl;
   }
   cout<<"END OF OUTPUT\n";
   return 0;
}