• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Why so serious? --[NKU]schindlerlee

            2010年1月13日星期三.sgu224 k皇后問題的位運算優化

            2010年1月13日星期三.sgu224
            k皇后問題的位運算優化
            這個是基本上學過編程的人都會寫過的程序。
            但是對于這個NP問題,只能搜索解決。如果寫的不好的話很容易超時。
            今天在Matrix67的文章中看到了使用位運算的方法,本來我還想用dancing links來
            搜一下呢,這個方法太精妙了!
            傳送門: http://www.matrix67.com/blog/archives/266

            我們知道(x&-x)是求x的最低位1,而這個操作是非常快的。
            在這個遞推過程中,只保存當前行的不可行解,然后利用求反和上邊說的求最低位1的方法對當前
            行的可行解進行遍歷,然后遞推求解

            不過這個不是n皇后問題,是k皇后,所以還需要對算法進行一些小小的改動。
            //http://www.shnenglu.com/schindlerlee/
            typedef 
            long long LL;
            const int N = 16;
            int n, k;

            #define bin(x) (1 << (x))
            #define L(x) ((x) << 1)
            #define R(x) ((x) >> 1)
            #define low(x) ((x) & -(x))

            int res = 0, full;
            //row代表列的狀態,ld代表左對角線,rd代表右對角線,cnt是已經使用的皇后數
            //line是已經推到了第幾第幾行
            void dfs(int row, int ld, int rd, int cnt, int line)
            {
              
            int p, t;
              
            if (line < n && cnt < k) {
                  t 
            = full & ~(row | ld | rd);
                  
            while (t != 0) {
                      p 
            = low(t);
                      t 
            ^= p;
                      dfs(row 
            + p, L(ld + p), R(rd + p), cnt + 1, line + 1);    //下一行
                  }
                  dfs(row, L(ld), R(rd), cnt, line 
            + 1);    //此行空
              } else if(cnt == k){
                  res
            ++;
              }

            }

            int main()
            {
              
            int i, j;
              scanf(
            "%d%d"&n, &k);
              full 
            = bin(n) - 1;
              dfs(
            00000);
              printf(
            "%d\n", res);
              
            return 0;
            }



            posted on 2010-01-13 22:52 schindlerlee 閱讀(1418) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            亚洲国产另类久久久精品小说| 久久精品毛片免费观看| 色偷偷91久久综合噜噜噜噜| 免费久久人人爽人人爽av| 亚洲精品乱码久久久久久久久久久久| 久久久久免费看成人影片| 国产精品免费久久久久影院| 久久免费看黄a级毛片| 婷婷综合久久狠狠色99h| 日韩影院久久| 亚洲国产精品热久久| 色偷偷久久一区二区三区| 久久精品亚洲福利| 久久发布国产伦子伦精品| 亚洲人成无码网站久久99热国产| 久久精品国产亚洲AV香蕉| 亚洲国产精品一区二区三区久久| 久久r热这里有精品视频| 国产美女亚洲精品久久久综合| 久久久久亚洲AV无码专区桃色| 久久精品国产精品亚洲毛片| 久久久噜噜噜久久中文字幕色伊伊 | 久久精品人人做人人爽97| 久久精品国产第一区二区| AV无码久久久久不卡网站下载 | 丰满少妇人妻久久久久久4| 日韩精品久久久肉伦网站| 色综合久久88色综合天天 | 久久播电影网| 国产999精品久久久久久| 精品国产乱码久久久久久1区2区| 亚洲а∨天堂久久精品9966| 久久久久黑人强伦姧人妻| 中文字幕一区二区三区久久网站| 国产精品久久午夜夜伦鲁鲁| 久久亚洲私人国产精品vA| 亚洲午夜久久久久久久久久| 久久天天躁狠狠躁夜夜躁2014| 久久免费视频1| 久久久久亚洲AV无码专区首JN| 久久久精品久久久久影院|