作者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)