算法实现题 战车问题

问题描述：在n*n格的棋盘上放置彼此不受攻击的车。按照国际象棋规则，车可以攻击与之处在同一行或同一列上的车。在棋盘上的若干个格中设置了堡垒，战车无法穿越堡垒攻击别的战车。对于给定的设置了堡垒的n*n格棋盘，设法放置尽可能多的彼此不受攻击的车。 算法设计：对于给定的设置了堡垒的n*n格棋盘，设计一个随机化算法，在棋盘上放置尽可能多的彼此不受攻击的车。 数据输入：由文件input.txt给出输入数据。第1行有1个正整数n。接下来的n行中，每行有1个字符“.”和“X”组成的长度为n的字符串。 结果输出：将计算的在棋盘上可以放置的彼此不受攻击的战车数输出到文件output.txt。

 
#include 
#include 
#include 


using namespace std;
const unsigned long maxshort = 65536L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
int* state;
int** link;
char** row;
class RandomNumber
{
private:
//当前种子
unsigned long randSeed;
public :
//构造函数，默认值0表示由系统自动产生种子
RandomNumber（unsigned long s =0 ）;
//产生0:n-1之间的随机整数
unsigned short Random（unsigned long n）;
//产生[01）之间的随机实数
double fRandom（void）;
};
//产生种子
RandomNumber::RandomNumber（unsigned long s）
{
if（s==0）randSeed = time（0）;//用系统时间产生种子
else randSeed = s;
}
//产生0:n-1之间的随机整数
unsigned short RandomNumber::Random（unsigned long n）
{
randSeed = multiplier * randSeed + adder;
return （unsigned short）（（randSeed>>16）%n）;
}
//产生[01）之间的随机实数
double RandomNumber::fRandom（void）
{
return Random（maxshort）/double（maxshort）;
}
bool MakeRow（char** &rowint rowsint cols）
{
row=new char* [rows];
for（int i=0;irow[i] = new char[cols];
return true;
}
bool Make2DArray（int** &linkint rowsint cols）
{

link=new int* [rows];
for（int i=0;ilink[i] = new int[cols];
return true;
}
void init（int n）
{
int ijkxy;

state=new int[n*n+2];
Make2DArray（linkn*n+12*n+1）;
state[0]=-1;
state[n*n+1]=-1;
for（int no=1;no<=n*n;no++）{
i=（no-1）/n;j=（no-1）%n;
link[no][0]=0;state[no]=-1;
if（row[i][j]==‘.‘）{
state[no]=0;k=0;y=j;
while（（ylink[no][0]++;y++;k++;
link[no][k]=i*n+y+1;
}
y=j;
while（（y>0）&&（row[i][y-1]==‘.‘））{
link[no][0]++;y--;k++;
link[no][k]=i*n+y+1;
}
x=i;
while（（xlink[no][0]++;x++;k++;
link[no][k]=x*n+j+1;
}
x=i;
while（（x>0）&&（row[x-1][j]==‘.‘））{
link[no][0]++;x--;k++;
link[no][k]=x*n+j+1;
}
}
}
}



int main（）
{
int nij;
RandomNumber rnd;
cout<<“输入棋盘的格数:“;
cin>>n;
cout<<“请输入棋盘上的布局:“<MakeRow（rown*n+12*n+1）;
for（i=0;ifor（j=0;jcin>>（char）row[i][j];
init（n）;

int max=0rept=0put=0;
while（rept<100000）{
rept++;int count=0;
while（true）{
int x=rnd.Random（n*n）+1c=x;
while（（x<=n*n）&&（state[x]!=put））x++;
if（state[x]!=put）{
x=c;
while（（x>0）&&（state[x]!=put））x--;
}
if（state[x]==put）{
count++;
for（i=1;i<=link[x][0];i++）
if（state[link[x][i]]==put）state[link[x][i]]++;
state[x]++;
}
else 
break;
}
if（count>max）max=count;
put++;
}

cout<<“最多可以放置战车数量:“<return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      74752  2007-02-28 14:38  战车问题\Debug\vc60.idb

     文件     110592  2007-02-28 14:38  战车问题\Debug\vc60.pdb

     文件     528431  2007-02-28 14:38  战车问题\Debug\战车问题.exe

     文件     784556  2007-02-28 14:38  战车问题\Debug\战车问题.ilk

     文件     256179  2007-02-28 14:38  战车问题\Debug\战车问题.obj

     文件    2005620  2007-02-28 14:38  战车问题\Debug\战车问题.pch

     文件    1090560  2007-02-28 14:38  战车问题\Debug\战车问题.pdb

     文件          0  2007-02-28 14:37  战车问题\战车问题.asp

     文件       2520  2007-02-28 14:38  战车问题\战车问题.cpp

     文件       4377  2007-02-28 14:38  战车问题\战车问题.dsp

     文件        541  2007-02-28 14:37  战车问题\战车问题.dsw

     文件      33792  2007-02-28 14:38  战车问题\战车问题.ncb

     文件      48640  2007-02-28 14:38  战车问题\战车问题.opt

     文件       1256  2007-02-28 14:38  战车问题\战车问题.plg

     目录          0  2007-02-28 14:38  战车问题\Debug

     目录          0  2007-02-28 14:38  战车问题

----------- ---------  ---------- -----  ----

              4941816                    16