?
#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:
//當(dāng)前種子
unsigned?long?randSeed;
public?:
//構(gòu)造函數(shù)，默認(rèn)值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子
RandomNumber（unsigned?long?s?=0?）;
//產(chǎn)生0:n-1之間的隨機(jī)整數(shù)
unsigned?short?Random（unsigned?long?n）;
//產(chǎn)生[01）之間的隨機(jī)實(shí)數(shù)
double?fRandom（void）;
};
//產(chǎn)生種子
RandomNumber::RandomNumber（unsigned?long?s）
{
if（s==0）randSeed?=?time（0）;//用系統(tǒng)時(shí)間產(chǎn)生種子
else?randSeed?=?s;
}
//產(chǎn)生0:n-1之間的隨機(jī)整數(shù)
unsigned?short?RandomNumber::Random（unsigned?long?n）
{
randSeed?=?multiplier?*?randSeed?+?adder;
return?（unsigned?short）（（randSeed>>16）%n）;
}
//產(chǎn)生[01）之間的隨機(jī)實(shí)數(shù)
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<<“輸入棋盤的格數(shù):“;
cin>>n;
cout<<“請(qǐng)輸入棋盤上的布局:“<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<<“最多可以放置戰(zhàn)車數(shù)量:“<return?0;
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件??????74752??2007-02-28?14:38??戰(zhàn)車問題\Debug\vc60.idb

?????文件?????110592??2007-02-28?14:38??戰(zhàn)車問題\Debug\vc60.pdb

?????文件?????528431??2007-02-28?14:38??戰(zhàn)車問題\Debug\戰(zhàn)車問題.exe

?????文件?????784556??2007-02-28?14:38??戰(zhàn)車問題\Debug\戰(zhàn)車問題.ilk

?????文件?????256179??2007-02-28?14:38??戰(zhàn)車問題\Debug\戰(zhàn)車問題.obj

?????文件????2005620??2007-02-28?14:38??戰(zhàn)車問題\Debug\戰(zhàn)車問題.pch

?????文件????1090560??2007-02-28?14:38??戰(zhàn)車問題\Debug\戰(zhàn)車問題.pdb

?????文件??????????0??2007-02-28?14:37??戰(zhàn)車問題\戰(zhàn)車問題.asp

?????文件???????2520??2007-02-28?14:38??戰(zhàn)車問題\戰(zhàn)車問題.cpp

?????文件???????4377??2007-02-28?14:38??戰(zhàn)車問題\戰(zhàn)車問題.dsp

?????文件????????541??2007-02-28?14:37??戰(zhàn)車問題\戰(zhàn)車問題.dsw

?????文件??????33792??2007-02-28?14:38??戰(zhàn)車問題\戰(zhàn)車問題.ncb

?????文件??????48640??2007-02-28?14:38??戰(zhàn)車問題\戰(zhàn)車問題.opt

?????文件???????1256??2007-02-28?14:38??戰(zhàn)車問題\戰(zhàn)車問題.plg

?????目錄??????????0??2007-02-28?14:38??戰(zhàn)車問題\Debug

?????目錄??????????0??2007-02-28?14:38??戰(zhàn)車問題

-----------?---------??----------?-----??----

??????????????4941816????????????????????16