che2.cpp

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

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

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

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

CRandomNum::CRandomNum(unsigned long s)
{
	if(s==0)
		nSeed=time(0);
	else 
		nSeed=s;
}

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


bool CheckPlaceChe(int **b,char **a,int x,int y,int n)  
{
	if(b[x][y]==1)return false;
	else
	{
		b[x][y]=1;
		if((y>=1)&&(y<=n)){     //上搜索 
			for(int i=y-1;i>=0;i--)
			{
		       	if ((b[x][i]==1) &&(a[x][i]=='X'))
			      break;
		        else 
				  b[x][i]=1;
			}
		}
         
		if((y<=n-1)&&(y>=0)){    //下搜索
			for(int i=y+1;i<n;i++)
			{
	    		if((b[x][i]==1)&&(a[x][i]=='X')) 
					break;
		   		else
		    		b[x][i]=1;
			}
		}
    	
		if((x>=1)&&(x<=n)){    //左搜索
			for(int j=x-1;j>=0;j--)
			{
				if((b[j][y]==1) &&(a[j][y]=='X'))
					break;
				else
			    	b[j][y]=1;
			}
		}

		if((x>=0)&&(x<=n-1)){    //右搜索
			for(int j=x+1;j<n;j++)
			{
		      if((b[j][y]==1) &&(a[j][y]=='X'))
				  break;
			   else
			   	  b[j][y]=1;
			}
		}
		return true;
	}
}


int MaxChes(int **b,char**a,int *x,int n)
{
	int max1=0;
	static CRandomNum rnd;
	for(int i=0;i<n;i++)    
	{
		bool flag=false;
		do
		{
            for(int j=0;j<n;j++){
			    if(b[i][j]==0){ flag=true;break;}
				else {flag=false;continue;}
			}

			if(flag){
		       x[i]=rnd.Random(n); 
		       if(CheckPlaceChe(b,a,i,x[i],n))
			      ++max1;
			}
	        
		}while(flag);
      
	}
	 	
	return max1;
}


int  main()
{
	ifstream fin("input.txt");
	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<15000)
	{
        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  max2=MaxChes(b,a,x,n);
	   if(max<max2) max=max2;
	   t++;
	}
	
	ofstream fout("output.txt");
	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;
}