作者kc655039 (NNN  )
看板ACMCLUB
标题[问题] 861
时间Wed Aug 31 00:56:39 2005
我解开但是怎麽更快呢,我是指用Backtracking,
我的作法是,如果把斜线分成偶数和奇数条,偶数不会撞到奇数,
再分开找出放k个棋子分别放在偶数条斜线和积数条斜线各有几种方法,
接下来就用 k个棋子中放在偶数条斜线上的*(k-放在偶数条斜线上的)的总和,
就求出k个棋子放在棋盘上的解法,然後分别从其盘是2求到八,
棋盘大小是1的时候我是直接把答案放到结果table里面,
这就是作法了......(希望能够被理解),
目前觉得应该可以推出来,就是不用暴力找解,
但实在很好奇就是.....我的backtracking总是没办法到最快.
所以想请大家如果也是使用backtracking解出来的....看看有没有什麽地方,
是很特别巧思.....可以给我参考参考
我把我的code贴在下方(如果不可以这样可以跟我说一声):
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void initial(bool *slash,bool *backslash)
{
int i;
for (i=0;i<15;i++)
slash[i]=backslash[i]=0;
}
bool validity(bool *slash,bool *backslash,int x,int y)
{
return !(slash[x+y] || backslash[x-y+7]);
}
//n是棋子,n减到变成零的时候就是一个solution
//x,y是启起始位置
//solution stands for the number of solutions.
//size means the size of checkboard.
void backtracking(int x,int y,int n,int *solution,int size,bool *slash,bool *backslash)
{
if (!n)
{
(*solution)++;
return;
}
int i,j;
for (i=x,j=y;i<size;i++)
{
while (j<size)
{
if (validity(slash,backslash,i,j))
{
slash[i+j]=backslash[i-j+7]=1;
backtracking(i,j,n-1,solution,size,slash,backslash);
slash[i+j]=backslash[i-j+7]=0;
}
j+=2;
}
if (j%2) j=0;
else j=1;
}
}
void answer(int table[][65])
{
int i,j,k;
int solution;
bool slash[15],backslash[15];
int black[65],white[65];//黑白分开
int result;
initial(slash,backslash);
for (i=1;i<9;i++)
table[i][0]=1;
table[1][1]=1;
for (i=2;i<9;i++)//the size of check board
{
black[0]=white[0]=1;//什麽都不放也算一种放法
for (j=1;j<i;j++)//j<i因为白色黑色部分最多只能放进去i-1个棋子(观察得知)
{
if (i%2)
{
//black goes first
solution=0;
backtracking(0,0,j,&solution,i,slash,backslash);
black[j]=solution;
//the tern of white
solution=0;
backtracking(0,1,j,&solution,i,slash,backslash);
white[j]=solution;
}
else
{
solution=0;
backtracking(0,0,j,&solution,i,slash,backslash);
black[j]=white[j]=solution;
}
}
for (j=1;j<=2*(i-1);j++)//j是棋盘上总共要摆几个棋子
{
result=0;
for (k=0;k<i;k++)
if (j-k<i && j-k>=0) result+=black[k]*white[j-k];
table[i][j]=result;
}
}
}
main()
{
int table[9][65]={0};
int n,k;
answer(table);
while (cin>>n>>k && n || k)
cout<<table[n][k]<<endl;
return 0;
}
.............maybe too long to read......
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.161.17.206
※ 编辑: kc655039 来自: 218.161.17.206 (08/31 00:58)
※ 编辑: kc655039 来自: 218.161.17.206 (08/31 01:00)