可用分押宝游戏火热进行中...	专题改版：Java Web 专题

4皇后问题变种（肯定不是4皇后那么简单）！进来吧。看看也好

楼主fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）2005-04-02 22:30:34 在 C/C++ / C语言提问

n阶矩阵（n<=4)
在一些空格里，放置障碍。皇后隔着障碍不会攻击。简单起见，斜线情况不攻击。也就是说，皇后不能在水平和垂直方向上遇到其它皇后（除非有障碍）。矩阵的障碍个数不定，位置不定，n<=4不定，求皇后最多的放置方法。
例如
。。。。
x 。x 。
。。。。
。。x x

我只想到用回溯，在每行情况下增加对有障碍情况下的递归。理论上应该可行。有没有哪位给个好的算法。帮帮忙，打开思路也好。问题点数：100、回复次数：13Top

1 楼ycom__net（一恒）回复于 2005-04-02 22:42:21 得分 10

其实算法大体一样，主要是判定的规则不同，

考虑递归，Top

2 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-04-02 22:44:26 得分 0

有没有其它思路？Top

3 楼ycom__net（一恒）回复于 2005-04-02 22:44:45 得分 0

貌似ZJU的1002Top

4 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-04-02 22:46:53 得分 0

晕菜。。。。
被发现了。。。就是这题垃圾Top

5 楼nasi00（莫傲·逍遥）回复于 2005-04-02 22:51:51 得分 5

规模也不大，搜索就好啦Top

6 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-04-02 22:56:23 得分 0

我当初一开始就是想到回溯。但我们老师说可以用权值，不用回溯。搞到我很郁闷。Top

7 楼yemin2004（peter_ye）回复于 2005-04-03 00:14:09 得分 5

可以用图的深度优先算法。。。Top

8 楼woodcord（我心飞翔）回复于 2005-04-03 07:19:21 得分 5

up一下！Top

9 楼arrowcy（长弓手）回复于 2005-04-03 11:35:36 得分 10

皇后最多的放置方法应该要在所有出现障碍的行或列放置两个皇后，可以从这方面考虑一下如果是人来放，在穷举之前应该怎样放，其实这个算法实现起来就是要先根据障碍位置穷举几种放法，然后对每一种放法，有穷举剩下的可能方法Top

10 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-04-03 11:43:12 得分 0

楼上的思路还是跟我的差不多。还是按照深度优先的方法回溯。有其它想法吗？我很纳闷我们老师说的给不同方格赋权值，然后按照权值来列优先级。我很怀疑他是不是吹牛皮。我想来想去都没有想到可以不用回溯穷举的。Top

11 楼syun0（@）回复于 2005-04-03 16:22:19 得分 10

可以把每个格子看成一个顶点,能够互相攻击的看成有边相连.
统计每个顶点相连的顶点数(你老师说的权值?),并生成一个邻接表.
然后在权值最小的点上放皇后,再将与它相连的点标为不可用,重复
这个过程,直到所有点都不可用.Top

12 楼pcboyxhy（-273.15℃）回复于 2005-04-03 19:41:26 得分 55

#include<iostream.h>

char *Street;
int n,l;
int MaxHouseNumber;

int CanPut(int X, int Y);
int TryHouse(int House, int X, int Y);

int main( )
{
int Index=0,Answer[2000];
while(cin>>n)
{
if(!n)
break;
Street=new char[n*n];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin>>*(Street+i*n+j);
MaxHouseNumber=0;
l=TryHouse(0, 0, 0);
Answer[Index++]=MaxHouseNumber;
delete Street;
}
for(int i=0; i<Index; i++)
cout<<Answer[i]<<endl;
return 0;
}

int TryHouse(int House, int X, int Y)
{
int IfCanPut;
if (House>MaxHouseNumber)
MaxHouseNumber=House;
IfCanPut=CanPut(X,Y);
if(Y+1<n)
{
if(IfCanPut)
{
House++;
*(Street+n*X+Y)='O';
}
TryHouse(House, X, Y+1);
if(IfCanPut)
{
House--;
*(Street+n*X+Y)='.';
}
TryHouse(House, X, Y+1);
}
else if(X+1<n)
{
if(IfCanPut)
{
House++;
*(Street+n*X+Y)='O';
}
TryHouse(House, X+1, 0);
if(IfCanPut)
{
House--;
*(Street+n*X+Y)='.';
}
TryHouse(House, X+1, 0);
}
else
{
if(IfCanPut)
House++;
if (House>MaxHouseNumber)
MaxHouseNumber=House;
return 0;
}
}

int CanPut(int X, int Y)
{
if(*(Street+X*n+Y)!='.')
return 0;
for(int b=X-1; b>=0; b--)
{
if(*(Street+b*n+Y)=='X')
break;
if(*(Street+b*n+Y)=='O')
return 0;
}
for(int b=Y-1; b>=0; b--)
{
if(*(Street+X*n+b)=='X')
break;
if(*(Street+X*n+b)=='O')
return 0;
}
return 1;
}

so easy
针对很多组数据写的
代码有些复杂，
当时不清楚输入输出格式。
不过最终还是AC了Top

13 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-04-03 21:57:31 得分 0

好的。我看看。谢了。你的分升的好快阿。三个月就裤衩变星了。Top