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

雪竹的天空

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>
            国产精品看片你懂得| 裸体一区二区| 亚洲午夜国产成人av电影男同| 欧美成人免费观看| 一本不卡影院| 亚洲一级在线| 黑人一区二区| 亚洲国产你懂的| 欧美精品一区三区在线观看| 亚洲天堂黄色| 午夜精品久久久久久久久久久 | 亚洲午夜高清视频| 国产亚洲成精品久久| 免费国产一区二区| 欧美日韩国产成人在线观看 | 一区二区亚洲欧洲国产日韩| 亚洲大胆美女视频| 国产伦精品一区二区三区视频黑人 | 国产日韩亚洲欧美| 亚洲高清毛片| 国产日产欧美精品| 亚洲国产精品成人va在线观看| 欧美日韩精品是欧美日韩精品| 欧美一区成人| 欧美日本成人| 美女精品在线观看| 国产精品二区二区三区| 蜜臀a∨国产成人精品| 欧美视频四区| 欧美黑人多人双交| 国产视频在线观看一区二区三区 | 欧美在线视频全部完| 亚洲免费观看在线视频| 欧美在线视频不卡| 亚洲欧美日韩精品久久| 狼人天天伊人久久| 欧美一区二区三区在线| 欧美日本在线看| 看片网站欧美日韩| 国产精品久久一级| 亚洲精品国精品久久99热| 国内久久视频| 亚洲欧美大片| 亚洲一区二区三区777| 免费在线日韩av| 久久亚洲一区二区三区四区| 国产精品美腿一区在线看| 亚洲人成在线播放| 亚洲精美视频| 久久影院午夜片一区| 久久激情五月激情| 国产精品视频福利| 一区二区三区视频在线观看| 99re6热只有精品免费观看| 久久亚洲综合网| 久久se精品一区二区| 国产精品久久777777毛茸茸| 亚洲精品国产无天堂网2021| 日韩午夜在线视频| 欧美大片免费看| 欧美国产日韩一区二区| 亚洲国产精品久久久久| 久久久久久久精| 亚洲在线国产日韩欧美| 久久精品国产久精国产一老狼 | 亚洲毛片一区二区| 亚洲看片免费| 欧美日韩精品一区二区在线播放 | 久久人人97超碰精品888| 久久综合国产精品台湾中文娱乐网| 国产日韩成人精品| 久久精品视频在线| 免费成人av在线看| 亚洲精品女人| 欧美日韩中国免费专区在线看| 一区二区av在线| 欧美一区二区久久久| 国产精品久久久久77777| 亚洲欧美日韩国产综合精品二区| 欧美在线免费视屏| 在线观看91精品国产麻豆| 免费av成人在线| 午夜一区不卡| 在线看欧美日韩| 欧美麻豆久久久久久中文| 在线亚洲精品福利网址导航| 欧美一区二区三区在线观看视频| 影音先锋亚洲精品| 欧美精品一区二区蜜臀亚洲| 亚洲午夜精品久久久久久浪潮| 久久精品国产亚洲一区二区| 亚洲国产精品免费| 国产精品久久久久77777| 午夜日韩电影| 91久久久久| 久久精品国产一区二区电影| 亚洲日本成人网| 国产精品男女猛烈高潮激情 | 亚洲精品乱码久久久久久久久| 性欧美在线看片a免费观看| 韩日欧美一区二区| 欧美日韩视频在线观看一区二区三区| 亚洲午夜视频在线| 欧美电影在线观看| 羞羞色国产精品| 亚洲第一二三四五区| 国产精品成人观看视频免费| 久久视频在线视频| 亚洲一区二区在线| 亚洲日本成人网| 久久久99免费视频| 亚洲在线免费观看| 日韩午夜在线播放| 亚洲大胆av| 欧美激情在线播放| 久久国产黑丝| 亚洲三级免费电影| 亚洲乱码国产乱码精品精可以看| 欧美日本精品一区二区三区| 欧美自拍丝袜亚洲| 亚洲视频在线视频| 亚洲美女毛片| 欧美激情一二三区| 蜜臀久久久99精品久久久久久| 午夜精品久久久久久久99热浪潮 | 欧美人与禽猛交乱配| 美女黄毛**国产精品啪啪| 久久精品一区二区三区不卡牛牛| 亚洲视频在线观看视频| 99ri日韩精品视频| 亚洲日韩视频| 亚洲欧洲久久| 亚洲欧洲美洲综合色网| 亚洲电影免费| 亚洲电影第1页| 亚洲国产日韩欧美在线图片| 男人的天堂亚洲在线| 久久久久欧美精品| 久久免费国产| 你懂的视频欧美| 欧美高清免费| 亚洲福利精品| 亚洲欧洲另类国产综合| 亚洲美女av在线播放| 亚洲美女黄网| 一区二区三区色| 亚洲一区二区在线观看视频| 亚洲一区二区三区在线播放| 亚洲视频一区二区| 午夜精品免费在线| 久久高清国产| 久热精品在线视频| 欧美高清在线| 欧美日精品一区视频| 国产精品萝li| 国产日韩专区| 在线日韩av片| 99视频精品全部免费在线| 亚洲午夜精品久久| 欧美在线一二三区| 蜜桃久久精品一区二区| 亚洲精品乱码久久久久久日本蜜臀| 亚洲美女精品久久| 欧美一级片一区| 美女图片一区二区| 欧美三级午夜理伦三级中文幕| 国产免费一区二区三区香蕉精| 国产一区二区三区在线观看免费| 影院欧美亚洲| 一二三区精品福利视频| 性久久久久久久| 亚洲第一伊人| 亚洲一区二区三区视频| 麻豆9191精品国产| 国产精品久久久久毛片大屁完整版 | 欧美一级视频| 欧美激情中文字幕乱码免费| 亚洲美女免费精品视频在线观看| 亚洲亚洲精品在线观看 | 99www免费人成精品| 久久av红桃一区二区小说| 欧美激情亚洲自拍| 国产一区二区无遮挡| 99国产精品国产精品久久| 欧美伊人久久| 亚洲精品在线视频| 久久精品一二三区| 国产精品爱久久久久久久| 精品99一区二区三区| 亚洲一区二区三区免费观看| 免费欧美日韩国产三级电影| 亚洲一区激情| 欧美日本免费| 亚洲片在线观看| 久久全球大尺度高清视频| 在线视频一区二区| 欧美日韩视频一区二区三区| 亚洲国产视频一区| 久久综合色播五月| 性欧美超级视频|