che1.cpp

战车问题 战车问题 战车问题 战车问题 战车问题 战车问题

#include<iostream.h>
#include<fstream.h>
#include<time.h>
#include<stdlib.h>


const unsigned long multiplier=1194211693l;
const unsigned long adder=12345l;

class freeNumber
{
private:
	unsigned long randSeed;
public:
	freeNumber(unsigned long s=0);    
	unsigned short free(unsigned long n);   
};

freeNumber::freeNumber(unsigned long s)
{
	if(s==0)
		randSeed=time(0);
	else 
		randSeed=s;
}

unsigned short freeNumber::free(unsigned long n)
{
	randSeed=multiplier*randSeed+adder;
	return (unsigned short)((randSeed>>16)%n);
}


bool CheckPlace(int **w,char **v,int x,int y,int n)  
{
	if(w[x][y]==1)return false;
	else
	{
		w[x][y]=1;
		    			
		if((x>=0)&&(x<=n-1)){    
			for(int j=x+1;j<n;j++)
			{
		      if((w[j][y]==1)&&(v[j][y]=='X'))
				  break;
			   else
			   	  w[j][y]=1;
			}
		}
     if((x>=1)&&(x<=n)){    
			for(int j=x-1;j>=0;j--)
			{
				if((w[j][y]==1)&&(v[j][y]=='X'))
					break;
				else
			    	w[j][y]=1;
			}
		}
         
		if((y<=n-1)&&(y>=0)){   
			for(int i=y+1;i<n;i++)
			{
	    		if((w[x][i]==1)&&(v[x][i]=='X')) 
					break;
		   		else
		    		w[x][i]=1;
			}
		}
       if((y>=1)&&(y<=n)){     
			for(int i=y-1;i>=0;i--)
			{
		       	if((w[x][i]==1)&&(v[x][i]=='X'))
			      break;
		        else
				  w[x][i]=1;
			}
		}
		return true;
	}
}


int Maxnum_Che(int **w,char**v,int *x,int n)
{
	int maxnum1=0;
	static freeNumber rnd;
	for(int i=0;i<n;i++)    
	{
		bool flag=false;
		do
		{
            for(int j=0;j<n;j++){
			    if(w[i][j]==0){ flag=true;break;}
				else {flag=false;continue;}
			}

			if(flag){
		       x[i]=rnd.free(n); 
		       if(CheckPlace(w,v,i,x[i],n))
			      ++maxnum1;
			}
	        
		}while(flag);
      
	}
	 	
	return maxnum1;
}


int  main()
{
	ifstream fin("input.txt");
	if(!fin)
	{
		cerr<<"can't open input.txt file!\n";
		exit(0);
	}
	int n;
	fin>>n;	
	 
	int **b=new int*[n];    
	for(int i=0;i<n;i++)
		b[i]=new int[n];

  char **a=new char*[n];   
	for( i=0;i<n;i++)
		a[i]=new char[n];

	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
		  fin>>a[i][j];
   
	
	   
	int maxnum=0;
	int *x=new int[n];
	for(i=0;i<n;i++)
		x[i]=0;
    
	int t=0;
	while(t<10000)
	{
        for(i=0;i<n;i++)
		{  for(int j=0;j<n;j++)
		   {
			 if(a[i][j]=='X')
			   	b[i][j]=1;
		    else
				b[i][j]=0;
		   }
		}
   
	   int  maxnum1=Maxnum_Che(b,a,x,n);
	   if(maxnum<maxnum1) maxnum=maxnum1;
	   t++;
	}
	
	ofstream fout("output.txt");
	if(!fout){
		cerr<<"can't open output.txt file!\n";
		exit(0);
	}
	fout<<maxnum;
    fin.close();
	fout.close();

	delete []x;
	
    for(i=0;i<n;i++)    
		delete[]b[i];
      delete []b;
   for(i=0;i<n;i++)    
		delete[]a[i];
	delete []a;	
	return 0;
}