[問題] 861

[kc655039 (￾NN￾N ￾  )]

我解開但是怎麼更快呢,我是指用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)