1066.cpp

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

#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
int p[4][2]={-1,0,0,-1,0,1,1,0};
int main(){
  ifstream cin("in.txt");
  int n,i,j,m,k,c=1;
  while(cin>>n&&n){
	 if(c>1) cout<<endl;
	 cout<<"Case "<<c++<<":\n\n";
     vector<int> tempa(n);vector<char> tempb(4*n+3,' ');
	 vector<vector<int> > input(n,tempa);vector<vector<char> > res(4*n-1,tempb);
	 for(i=0;i<4*n+3;i++) {res[0][i]='*';res[4*n-2][i]='*';}
	 for(i=0;i<4*n-1;i++) {res[i][0]='*';res[i][4*n+2]='*';}
	 for(i=1;i<4*n-1;i+=4){
		 for(j=3;j<4*n+3;j+=4)
			 res[i][j]='O';
	 }
	 for(i=1;i<4*n-1;i+=4){
		 for(j=1;j<4*n+3;j+=4)
			 res[i][j]='H';
	 }
	 for(i=3;i<4*n-1;i+=4){
		 for(j=3;j<4*n+3;j+=4)
			 res[i][j]='H';
	 }
	 for(i=0;i<n;i++)
		 for(j=0;j<n;j++){
			 cin>>input[i][j];
             if(input[i][j]==1){res[i*4+1][j*4+2]=res[i*4+1][j*4+4]='-';}
			 if(input[i][j]==-1){res[i*4+2][j*4+3]=res[i*4][j*4+3]='|';}
		 }
	 for(i=1;i<4*n-1;i++){
		 for(j=1;j<4*n+3;j++)
			 if(res[i][j]=='H'){
                 m=0;
				 for(k=0;k<4;k++)
                    if(res[i+p[k][0]][j+p[k][1]]=='-'||res[i+p[k][0]][j+p[k][1]]=='|')
						m=1;
			     if(m==0){
                     for(k=0;k<4;k++){
                         int oi=i+2*p[k][0],oj=j+2*p[k][1];
						 if(oi>=0&&oj>=0&&oi<4*n-1&&oj<4*n+3&&input[(oi-1)/4][(oj-3)/4]!=1&&input[(oi-1)/4][(oj-3)/4]!=-1&&input[(oi-1)/4][(oj-3)/4]!=20){
                              input[(oi-1)/4][(oj-3)/4]+=10;
							  if(k==1||k==2) res[i+p[k][0]][j+p[k][1]]='-';
							  else res[i+p[k][0]][j+p[k][1]]='|';
							  break;
						 }
					 }
				 }
			 }
	 }
	 for(i=0;i<4*n-1;i++){
		 for(j=0;j<4*n+3;j++)
			 cout<<res[i][j];
		 cout<<endl;
	 }
  }
}