040320161.cpp

在n×n 格的棋盘上放置彼此不受攻击的车。按照国际象棋的规则

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

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

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

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

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


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

		if((t>=0)&&(t<=n-1)){
			for(int j=t+1;j<n;j++)
			{
		      if((w[j][k]==1)&&(v[j][k]=='X'))
				  break;
			   else
			   	  w[j][k]=1;
			}
		}
		return true;
	}
}


int Che_search(int **w,char**v,int *x,int n)
{
	int max1=0;
	static RandomNumber 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.Random(n); 
		       if(place(w,v,i,x[i],n))
			      ++max1;
			}
	        
		}while(flag);
      
	}
	 	
	return max1;
}


int  main()
{
	ifstream fin("input.txt");
	if(!fin)
	{
		cerr<<"can't open input.txt file!\n";
		exit(0);
	}
	int n;
	fin>>n;
	char **a=new char*[n];
	for(int 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 **b=new int*[n];
	for(i=0;i<n;i++)
		b[i]=new int[n];
	
	   
	int max=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  max1=Che_search(b,a,x,n);
	   if(max<max1) max=max1;
	   t++;
	}
	
	ofstream fout("output.txt");
	if(!fout){
		cerr<<"can't open output.txt file!\n";
		exit(0);
	}
	fout<<max;
    fin.close();
	fout.close();

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