王敏-2.5分.txt

这是很不错的计算机算法

#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

long n;//棋盘的大小
int num;//可放置战车数
char * * chessBoard;//存放棋盘信息
char * * mychessBoard;//存放动态棋盘信息
unsigned long randSeed=time(NULL);//用系统时间初始化随机种子
const unsigned long multiplier=1194211693L;//乘数
const unsigned long adder=12345L;//加数

unsigned short Random(unsigned long n)//计算随机值
{
	randSeed=multiplier*randSeed+adder;
	return (unsigned short)((randSeed>>16)%n);
}

void Place(int i,int j)
{
	if(i!=n)//不是最后一行
	{
		int k=i;//从放置行出发
		while(k<=n&&mychessBoard[k][j]=='.')//将后续行该列上与放置位置冲突点做标记
		{
			mychessBoard[k][j]='o';
			k++;//下一行
		}
	}
}

int ChessLV()
{
	int i,j,k,p;//循环控制变量
	int count=0;//可放战车数
	for(i=1;i<=n;i++)//复制棋盘信息
		for(j=1;j<=n;j++)
			mychessBoard[i][j]=chessBoard[i][j];
	for(k=1;k<=n;k++)//分析每一行
	{
		i=1;//寻找起点
		j=1;//列号
		while(j<=n)
		{
			//计算从行首开始直到堡垒处共有多少位置（j-1个，其中包括不可放置点）
                        while(j<=n&&mychessBoard[k][j]!='X')
                                j++;
			if(j!=i)//如果有可放点
			{
				int index;//放置战车的列号
				int mycount;//是否有位置可放标记
				mycount=0;
				for(p=i;p<j;p++)//搜索每个可放点
					if(mychessBoard[k][p]=='.')//如果该点可放置战车
						if(Random(++mycount)==0)//随机选择一个位置
							index=p;
				if(mycount>0)//如果有位置可放战车
				{
					Place(k,index);//设定与该位置冲突标记
					mychessBoard[k][index]='F';//该位置已放，做标记
					count++;//战车数加1
				}
			}
			j++;//在该行从堡垒处出发继续寻找
			i=j;//设定新的起点
		}
	}
	return count;//返回战车数
}

void main()
{
	int i,j;//循环控制变量
	ifstream fin("input.txt",ios::nocreate);//打开输入文件
	if(fin.fail())//文件不存在
	{
		cout<<"the input.txt is not exist!";
		exit(1);//退出
	}
		fin>>n;//读入棋盘大小
		if(n>0)//如果非零
		{
			chessBoard=new char * [n+1];//为棋盘分配空间
			for(i=0;i<=n;i++)
				chessBoard[i]=new char[n+1];
			mychessBoard=new char * [n+1];
			for(i=0;i<=n;i++)
				mychessBoard[i]=new char[n+1];
			for(i=1;i<=n;i++)//读入棋盘信息
				for(j=1;j<=n;j++)
					fin>>chessBoard[i][j];
				int k;//循环次数
				k=10000;
				for(i=0;i<=k;i++)
				{
					int mid;//所求的战车数
					mid=ChessLV();//计算可放置战车数
					if(mid>num)//如果此时所求数值更大，则更新
						num=mid;
				}

			}
	
		ofstream out("output.txt");//创建输出文件
		out<<num<<endl;//输出战车数到文件
        fin.close();//关闭输入文件
		out.close();//关闭输出文件
}