青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

雪竹的天空

theorix

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
  34 隨筆 :: 0 文章 :: 20 評論 :: 0 Trackbacks

 數獨問題可以轉換為729行324列的exact cover 問題。每一行代表每個方格的可選值,每一列代表每個格的限制,建立雙向十字鏈表,即可用dancing links算法優化求解。

  1Source Code
  2
  3Problem: 3074  User: theorix 
  4Memory: 308K  Time: 47MS 
  5Language: C++  Result: Accepted 
  6
  7Source Code 
  8#include<iostream>
  9using namespace std;
 10#define RR 729
 11#define CC 324
 12#define INF 1000000000
 13int mem[RR+9];
 14int ans[RR+9];
 15char ch[RR+9];
 16int cnt[CC+9];
 17struct node
 18{
 19    int r,c;
 20    node *up;
 21    node *down;
 22    node *left;
 23    node *right;
 24}
head,all[RR*CC+99],row[RR],col[CC];int all_t;
 25inline void link(int r,int c)
 26{
 27    cnt[c]++;
 28    node *t=&all[all_t++];
 29    t->r=r;
 30    t->c=c;
 31    t->left=&row[r];
 32    t->right=row[r].right;
 33    t->left->right=t;
 34    t->right->left=t;
 35    t->up=&col[c];
 36    t->down=col[c].down;
 37    t->up->down=t;
 38    t->down->up=t;
 39}

 40inline void remove(int c)
 41{
 42    node *t,*tt;
 43    col[c].right->left=col[c].left;
 44    col[c].left->right=col[c].right;
 45    for(t=col[c].down;t!=&col[c];t=t->down)
 46    {
 47        for(tt=t->right;tt!=t;tt=tt->right)
 48        {
 49            cnt[tt->c]--;
 50            tt->up->down=tt->down;
 51            tt->down->up=tt->up;
 52        }

 53        t->left->right=t->right;
 54        t->right->left=t->left;
 55    }

 56}

 57inline void resume(int c)
 58{
 59    node *t,*tt;
 60    for(t=col[c].down;t!=&col[c];t=t->down)
 61    {        
 62        t->right->left=t;
 63        t->left->right=t;
 64        for(tt=t->left;tt!=t;tt=tt->left)
 65        {
 66            cnt[tt->c]++;
 67            tt->down->up=tt;
 68            tt->up->down=tt;
 69        }

 70    }
    
 71    col[c].left->right=&col[c];
 72    col[c].right->left=&col[c];
 73}

 74bool solve(int k)
 75{
 76    if(head.right==&head)
 77        return true;
 78    node*t,*tt;
 79    int min=INF,tc;
 80    for(t=head.right;t!=&head;t=t->right)
 81    {
 82        if(cnt[t->c]<min)
 83        {
 84            min=cnt[t->c];
 85            tc=t->c;
 86            if(min<=1)break;
 87        }

 88    }

 89    remove(tc);
 90    for(t=col[tc].down;t!=&col[tc];t=t->down)
 91    {
 92        mem[k]=t->r;
 93        t->left->right=t;
 94        for(tt=t->right;tt!=t;tt=tt->right)
 95        {
 96            remove(tt->c);
 97        }

 98        t->left->right=t->right;
 99        if(solve(k+1))
100            return true;
101        t->right->left=t;
102        for(tt=t->left;tt!=t;tt=tt->left)
103        {
104            resume(tt->c);
105        }

106        t->right->left=t->left;
107    }

108    resume(tc);
109    return false;
110}

111int main()
112{
113    double ss=0;
114    while(gets(ch))
115    {
116        int i,j,k;
117        if(ch[0]=='e')break;
118        all_t=1;
119        memset(cnt,0,sizeof(cnt));
120        head.left=&head;
121        head.right=&head;
122        head.up=&head;
123        head.down=&head;
124        head.r=RR;
125        head.c=CC;
126        for(i=0;i<CC;i++)
127        {
128            col[i].c=i;
129            col[i].r=RR;
130            col[i].up=&col[i];
131            col[i].down=&col[i];
132            col[i].left=&head;
133            col[i].right=head.right;
134            col[i].left->right=&col[i];
135            col[i].right->left=&col[i];
136        }

137        for(i=0;i<RR;i++)
138        {
139            row[i].r=i;
140            row[i].c=CC;
141            row[i].left=&row[i];
142            row[i].right=&row[i];
143            row[i].up=&head;
144            row[i].down=head.down;
145            row[i].up->down=&row[i];
146            row[i].down->up=&row[i];
147        }

148        for(i=0;i<RR;i++)
149        {
150            int r=i/9/9%9;
151            int c=i/9%9;
152            int val=i%9+1;
153            if(ch[r*9+c]=='.'||ch[r*9+c]==val+'0')
154            {
155                link(i,r*9+val-1);
156                link(i,81+c*9+val-1);
157                int tr=r/3;
158                int tc=c/3;
159                link(i,162+(tr*3+tc)*9+val-1);
160                link(i,243+r*9+c);
161            }

162        }

163        for(i=0;i<RR;i++)
164        {
165            row[i].left->right=row[i].right;
166            row[i].right->left=row[i].left;
167        }

168        solve(1);
169        for(i=1;i<=81;i++)
170        {
171            int t=mem[i]/9%81;
172            int val=mem[i]%9+1;
173            ans[t]=val;
174        }

175        for(i=0;i<81;i++)
176            printf("%d",ans[i]);
177        printf("\n");
178    }

179}

180
181

 

posted on 2008-09-01 02:01 雪竹的天空( theorix ) 閱讀(5844) 評論(8)  編輯 收藏 引用 所屬分類: 解題報告

評論

# re: 數獨的 Dancing links 解法(源代碼) 2008-09-01 02:12 <font color="red">雪竹的天空( theorix )
TLE了幾天終于把這道數獨題過了
呵呵 寫的還不錯  回復  更多評論
  

# re: 數獨的 Dancing links 解法(含源代碼) 2008-11-27 16:39 梅雪香
您好,向您請教一下,這個程序的輸入數據格式是怎么樣的呢?
另外,我基本了解了dancing links的求解算法,但不太清楚如何把數獨問題轉化為精確覆蓋問題,也就是怎么初始化成為729行324列的exact cover 問題。
能不能把這個轉換過程的思想描述一下呢?
如肯賜教請發郵件到: mxx@vip.qq.com
先謝謝您了.  回復  更多評論
  

# re: 數獨的 Dancing links 解法(含源代碼) 2009-02-08 23:18 stranger
http://en.wikipedia.org/wiki/Exact_cover  回復  更多評論
  

# re: 數獨的 Dancing links 解法(含源代碼) 2009-02-25 14:37 ttylikl
我將上面的代碼移植到C#竟然出了問題,真暈啊。。。  回復  更多評論
  

# re: 數獨的 Dancing links 解法(含源代碼) 2009-06-03 20:41 doxi
想問問,但如何把數獨問題轉化為精確覆蓋問題 謝謝大牛指點  回復  更多評論
  

# re: 數獨的 Dancing links 解法(含源代碼) 2009-06-03 20:42 doxi

想問問,但如何把數獨問題轉化為精確覆蓋問題 謝謝大牛指點 doxi
我的郵箱 ; fanxicai2000@163.com  回復  更多評論
  

# re: 數獨的 Dancing links 解法(含源代碼) 2010-05-08 15:46 批你
靠啊,你確定你是對的嗎  回復  更多評論
  

# re: 數獨的 Dancing links 解法(含源代碼) 2010-09-26 15:02 LitIce
我認真研究了下你的程序,用他做noip2009靶形數獨。
發現
102 for(tt=t->left;tt!=t;tt=tt->left)
如果把left改成right。。(其他對應)改動。
也就是恢復的順序和刪除的順序相同,會Tle。
而你現在這樣原路退回去恢復會快很多,并且不會Tle.
能否解釋下。
郵箱:13559542150@139.com
期待你的回復……
90 for(t=col[tc].down;t!=&col[tc];t=t->down)
91 {
92 mem[k]=t->r;
93 t->left->right=t;
94 for(tt=t->right;tt!=t;tt=tt->right)
95 {
96 remove(tt->c);
97 }
98 t->left->right=t->right;
99 if(solve(k+1))
100 return true;
101 t->right->left=t;
102 for(tt=t->left;tt!=t;tt=tt->left)
103 {
104 resume(tt->c);
105 }
106 t->right->left=t->left;
107 }
  回復  更多評論
  

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品丝袜久久久久久app| 久久久久久久一区二区| 亚洲欧洲精品一区| 亚洲人体大胆视频| 亚洲国产精品久久91精品| 一区二区三区波多野结衣在线观看| 国产精品99久久久久久宅男| 久久精品主播| 久久综合成人精品亚洲另类欧美| 欧美剧在线免费观看网站| 国产精品天美传媒入口| 久久蜜臀精品av| 一区二区日韩精品| 男女精品视频| 狠狠色2019综合网| 在线视频精品一区| 欧美一区2区三区4区公司二百| 欧美激情一二区| 伊人久久婷婷| 久久精品一二三| 欧美大秀在线观看| 亚洲国产二区| 麻豆久久婷婷| 欧美亚洲一区二区在线观看| 91久久精品网| 亚洲已满18点击进入久久| 欧美日韩精品伦理作品在线免费观看| 国产亚洲综合在线| 欧美一区2区视频在线观看| 亚洲伦理一区| 欧美日韩国产首页在线观看| 久久精品亚洲一区| 香蕉成人伊视频在线观看| 国产精品男人爽免费视频1| 亚洲午夜一区二区三区| 99国产精品自拍| 欧美性猛交xxxx乱大交蜜桃 | 性色av一区二区三区在线观看| 亚洲高清一区二| 亚洲一区二区三区精品在线观看| 亚洲国产高清一区| 欧美在线资源| 激情欧美一区二区三区| 欧美成人精品| 嫩模写真一区二区三区三州| 久久精品天堂| 国产精品日韩欧美一区二区| 亚洲精品在线观看视频| 亚洲茄子视频| 久久噜噜亚洲综合| 亚洲欧洲三级电影| 久久视频免费观看| 亚洲最新在线视频| 一区二区三区日韩| 99精品视频免费观看视频| 亚洲精品久久嫩草网站秘色| 国产精品vvv| 亚洲看片免费| 夜夜嗨av一区二区三区四区| 欧美激情亚洲国产| 亚洲丰满少妇videoshd| 欧美日韩一区视频| 久久久久久69| 韩国视频理论视频久久| 西西人体一区二区| 久久久国产精品一区二区中文| 国产精品视频不卡| 午夜精品久久久久久久久久久久久 | 亚洲精品国产系列| 一区二区三区四区五区精品视频| 国产精品久久久久天堂| 一区二区三区久久| 亚洲欧美一区二区视频| 美日韩在线观看| 亚洲一区二区三区成人在线视频精品| 欧美日韩 国产精品| 99视频精品在线| 午夜精品理论片| 国产一区二区三区最好精华液| 久久精品亚洲国产奇米99| 亚洲一区二区三区影院| 国产精品人人爽人人做我的可爱| 亚洲欧美日韩一区二区三区在线| 久久精品91久久香蕉加勒比| 1769国内精品视频在线播放| 亚洲色图在线视频| 久久av老司机精品网站导航| 欧美日韩在线观看一区二区三区| 一区二区三区三区在线| 久久精品视频网| 亚洲国产精品视频一区| 欧美色偷偷大香| 亚洲日本aⅴ片在线观看香蕉| 亚洲深夜福利视频| 韩日成人av| 欧美激情综合在线| 亚洲欧美日韩直播| 欧美激情第一页xxx| 韩国免费一区| 欧美理论视频| 久久国产高清| 久久精品视频免费| 日韩视频免费观看高清完整版| 久久午夜色播影院免费高清| 亚洲美女啪啪| 在线亚洲精品| 国产一区美女| 欧美一区二区三区免费看| 亚洲第一精品在线| 欧美在线视频免费| 一本到高清视频免费精品| 国产视频在线观看一区| 午夜欧美大片免费观看| 亚洲精品视频在线| 猛干欧美女孩| 亚洲精品看片| 韩国v欧美v日本v亚洲v| 欧美特黄a级高清免费大片a级| 久久这里只有| 欧美一区二区私人影院日本| 亚洲美女尤物影院| 亚洲国产精品国自产拍av秋霞| 欧美一区午夜精品| 亚洲综合导航| 国产在线拍揄自揄视频不卡99| 欧美日韩综合一区| 欧美日韩精品二区第二页| 蜜臀久久99精品久久久久久9| 欧美资源在线观看| 性色av一区二区三区| 亚洲欧美激情视频| 美日韩精品免费| 久久久噜噜噜久久| 久久精品国产在热久久| 欧美在线黄色| 欧美在线看片| 久久激情婷婷| 久久精品综合| 蜜桃久久av一区| 美腿丝袜亚洲色图| 亚洲成人资源网| 亚洲自拍电影| 亚洲一区二区毛片| 亚洲欧美综合国产精品一区| 亚洲欧美影音先锋| 亚久久调教视频| 在线观看一区| 亚洲国产精品久久久| 亚洲国产综合在线看不卡| 欧美性一二三区| 国产精品久久久一本精品| 国产精品美女在线观看| 国产精品专区第二| 欧美高清视频一二三区| 午夜精品免费| 欧美中在线观看| 米奇777在线欧美播放| 欧美激情偷拍| 国产精品乱人伦一区二区| 国产精品视频成人| 在线播放亚洲一区| 亚洲精一区二区三区| 亚洲视频精选| 久久午夜视频| 午夜精品久久久久久久男人的天堂| 性欧美videos另类喷潮| 老司机免费视频久久| 亚洲黄色一区| 欧美电影免费观看高清| 欧美在线欧美在线| 男女激情视频一区| 这里只有精品丝袜| 久久久av毛片精品| 欧美婷婷久久| 在线观看久久av| 亚洲视屏在线播放| 老司机aⅴ在线精品导航| 亚洲精品视频在线| 久久都是精品| 欧美性大战久久久久久久| 狠狠噜噜久久| 亚洲欧美日韩国产中文在线| 亚洲午夜在线观看视频在线| 久久久精品国产免大香伊 | 亚洲私拍自拍| 可以看av的网站久久看| 99精品国产一区二区青青牛奶| 久久精品国产一区二区电影| 欧美性jizz18性欧美| 91久久久国产精品| 久久精品首页| 亚洲图片欧洲图片av| 中日韩视频在线观看| 蜜臀av一级做a爰片久久| 国产日韩亚洲欧美| 亚洲在线视频网站| 欧美激情在线播放| 久久免费视频一区| 国产亚洲欧美日韩一区二区| 亚洲一级高清|