NOI2005 智慧珠游戏

Posted on 2011-07-20 23:07 Mato_No1 阅读(1119) 评论(2)  编辑 收藏 引用 所属分类: 搜索NOI
【原题见这里
很明显的精确覆盖的模型,12个零件,再加上它们经过旋转、翻转后的不同形状,共60种,每种又可以放在不同的位置(只看最左上的那个珠子)一种零件的一种位置就是一行。列(限制)有两种:每个格子只能放一个(55列),以及每个零件(注意是每个零件,不是每种零件)只能用一次(12列),共67列。预先放的那些零件可以看成预先选中的行。然后DLX精确覆盖即可。

下面是DLX精确覆盖的几个易疵点:
(1)整个矩阵的行数和列数不能疵(比如本题是1644行,67列);
(2)注意init_d()、add_node(int, int)、delcol(int)、resucol(int)中的一些细节:
【1】init_d()中,是否把m写成了n;
【2】add_node(int, int)中,是否写了cols[c]++;
【3】delcol(int)和resucol(int)中,变量有木有疵(比如把i写成j之类的),另外是否对cols进行了处理;
(3)如果有一些行预先被选中,注意在删掉这些行的时候是否删光,不要漏了行头(rowh);
(4)注意区分行号、列号和结点下标,delcol(int x)和resucol(int x)中的参数x一定是列号,而记录可行解的res数组里存放的一定是行号;
(5)结点的行、列号均从1开始(第0行、第0列有特殊意义);
(6)如果有多组数据,检查在每组数据之前是否将所有数组初始化;

本题代码:
#include <iostream>
#include 
<stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define set(i, j, x, y) PX[i][j] = x; PY[i][j] = y;
const int S = 10, n = 1644, m = 67, T = 60, INF = ~0U >> 2;;
const int LL[12= {046141519273139474852}, RR[12= {3513141826303846475159};
const char SSS[T + 1= "AAAABBCCCCCCCCDEEEEFFFFFFFFGGGGHHHHHHHHIIIIIIIIJKKKKLLLLLLLL";
struct dlnode {
    
int r, c, U, D, L, R;
} d[(n 
+ 1* (m + 1)];
int rowh[n + 1], cols[m + 1], nodes, PX[T][5], PY[T][5], len[T], No[S][S], pos[n + 1][3], _pos[T][S][S], res[n], res_len;
char a[S][S];
bool vst[12];
void init_d()
{
    re3(i, 
0, m) {d[i].U = d[i].D = i; d[i].L = i - 1; d[i].R = i + 1;} d[0].L = m; d[m].R = 0; nodes = m;
    re1(i, n) rowh[i] 
= -1;
    re1(i, m) cols[i] 
= 0;
}
void add_node(int r, int c)
{
    cols[c]
++; d[++nodes].r = r; d[nodes].c = c; d[nodes].U = d[c].U; d[nodes].D = c; d[c].U = nodes; d[d[nodes].U].D = nodes;
    
int rh = rowh[r]; if (rh == -1) d[nodes].L = d[nodes].R = rowh[r] = nodes; else {
        d[nodes].L 
= d[rh].L; d[nodes].R = rh; d[rh].L = nodes; d[d[nodes].L].R = nodes;
    }
}
void init()
{
    freopen(
"zhzyx.in""r", stdin);
    
char ch;
    re(i, S) {
        re(j, i
+1) a[i][j] = getchar();
        ch 
= getchar();
    }
    fclose(stdin);
}
void delLR(int x)
{
    d[d[x].L].R 
= d[x].R; d[d[x].R].L = d[x].L;
}
void resuLR(int x)
{
    d[d[x].L].R 
= d[d[x].R].L = x;
}
void delUD(int x)
{
    d[d[x].U].D 
= d[x].D; d[d[x].D].U = d[x].U;
}
void resuUD(int x)
{
    d[d[x].U].D 
= d[d[x].D].U = x;
}
void delcol(int x)
{
    delLR(x); 
for (int i=d[x].D; i != x; i=d[i].D) for (int j=d[i].R; j != i; j=d[j].R) {cols[d[j].c]--; delUD(j);}
}
void resucol(int x)
{
    
for (int i=d[x].U; i != x; i=d[i].U) for (int j=d[i].L; j != i; j=d[j].L) {resuUD(j); cols[d[j].c]++;} resuLR(x);
}
void prepare()
{
    init_d();
    len[
0= 3set(0000); set(0101); set(0210);
    len[
1= 3set(1000); set(1101); set(1211);
    len[
2= 3set(2000); set(2110); set(2211);
    len[
3= 3set(3000); set(3110); set(321-1);
    len[
4= 4set(4000); set(4101); set(4202); set(4303);
    len[
5= 4set(5000); set(5110); set(5220); set(5330);
    len[
6= 4set(6000); set(6101); set(6202); set(6310);
    len[
7= 4set(7000); set(7101); set(7202); set(7312);
    len[
8= 4set(8000); set(8110); set(8211); set(8312);
    len[
9= 4set(9000); set(9110); set(921-1); set(931-2);
    len[
10= 4set(10000); set(10101); set(10210); set(10320);
    len[
11= 4set(11000); set(11101); set(11211); set(11321);
    len[
12= 4set(12000); set(12110); set(12220); set(12321);
    len[
13= 4set(13000); set(13110); set(13220); set(1332-1);
    len[
14= 4set(14000); set(14101); set(14210); set(14311);
    len[
15= 5set(15000); set(15110); set(15220); set(15321); set(15422);
    len[
16= 5set(16000); set(16110); set(16220); set(1632-1); set(1642-2);
    len[
17= 5set(17000); set(17101); set(17202); set(17310); set(17420);
    len[
18= 5set(18000); set(18101); set(18202); set(18312); set(18422);
    len[
19= 5set(19000); set(19101); set(19202); set(19303); set(19411);
    len[
20= 5set(20000); set(20101); set(20202); set(20303); set(20412);
    len[
21= 5set(21000); set(2111-1); set(21210); set(21311); set(21412);
    len[
22= 5set(22000); set(2211-2); set(2221-1); set(22310); set(22411);
    len[
23= 5set(23000); set(23110); set(23211); set(23320); set(23430);
    len[
24= 5set(24000); set(24110); set(2421-1); set(24320); set(24430);
    len[
25= 5set(25000); set(25110); set(25220); set(25321); set(25430);
    len[
26= 5set(26000); set(26110); set(26220); set(2632-1); set(26430);
    len[
27= 5set(27000); set(27101); set(27202); set(27310); set(27412);
    len[
28= 5set(28000); set(28110); set(28211); set(28302); set(28412);
    len[
29= 5set(29000); set(29101); set(29210); set(29320); set(29421);
    len[
30= 5set(30000); set(30101); set(30211); set(30320); set(30421);
    len[
31= 5set(31000); set(31101); set(31202); set(31310); set(31411);
    len[
32= 5set(32000); set(32101); set(32202); set(32311); set(32412);
    len[
33= 5set(33000); set(33101); set(33210); set(33311); set(33412);
    len[
34= 5set(34000); set(34101); set(3421-1); set(34310); set(34411);
    len[
35= 5set(35000); set(35101); set(35210); set(35311); set(35420);
    len[
36= 5set(36000); set(36101); set(36210); set(36311); set(36421);
    len[
37= 5set(37000); set(37110); set(37211); set(37320); set(37421);
    len[
38= 5set(38000); set(3811-1); set(38210); set(3832-1); set(38420);
    len[
39= 5set(39000); set(39101); set(39202); set(39312); set(39413);
    len[
40= 5set(40000); set(40101); set(40202); set(4031-1); set(40410);
    len[
41= 5set(41000); set(41101); set(41211); set(41312); set(41413);
    len[
42= 5set(42000); set(42101); set(4221-2); set(4231-1); set(42410);
    len[
43= 5set(43000); set(43110); set(43220); set(43321); set(43431);
    len[
44= 5set(44000); set(44110); set(4422-1); set(44320); set(4443-1);
    len[
45= 5set(45000); set(45110); set(45211); set(45321); set(45431);
    len[
46= 5set(46000); set(4611-1); set(46210); set(4632-1); set(4643-1);
    len[
47= 5set(47000); set(4711-1); set(47210); set(47311); set(47420);
    len[
48= 5set(48000); set(48110); set(48211); set(48321); set(48422);
    len[
49= 5set(49000); set(4911-1); set(49210); set(4932-2); set(4942-1);
    len[
50= 5set(50000); set(50101); set(50211); set(50312); set(50422);
    len[
51= 5set(51000); set(51101); set(5121-1); set(51310); set(5142-1);
    len[
52= 5set(52000); set(52101); set(52202); set(52303); set(52410);
    len[
53= 5set(53000); set(53101); set(53202); set(53303); set(53413);
    len[
54= 5set(54000); set(5411-3); set(5421-2); set(5431-1); set(54410);
    len[
55= 5set(55000); set(55110); set(55211); set(55312); set(55413);
    len[
56= 5set(56000); set(56101); set(56210); set(56320); set(56430);
    len[
57= 5set(57000); set(57101); set(57211); set(57321); set(57431);
    len[
58= 5set(58000); set(58110); set(58220); set(58330); set(58431);
    len[
59= 5set(59000); set(59110); set(59220); set(5933-1); set(59430);
    
int No0 = 0, x0, y0, z; re(i, S) re(j, i+1) No[i][j] = ++No0;
    
bool ff;
    No0 
= 0; re(i, T) re(x, S) re(y, x+1) {
        ff 
= 1; re(j, len[i]) {
            x0 
= x + PX[i][j]; y0 = y + PY[i][j];
            
if (x0 < 0 || x0 >= S || y0 < 0 || y0 >= S || x0 < y0) {ff = 0break;}
        }
        
if (ff) {
            No0
++; pos[No0][0= i; pos[No0][1= x; pos[No0][2= y; _pos[i][x][y] = No0;
            re(j, len[i]) {x0 
= x + PX[i][j]; y0 = y + PY[i][j]; add_node(No0, No[x0][y0]);} add_node(No0, 55 + SSS[i] - 64);
        }
    }
    re(i, 
12) vst[i] = 0;
    
int _x, rh;
    re(x, S) re(y, x
+1if (a[x][y] != '.') {
        z 
= a[x][y] - 65;
        
if (!vst[z]) {
            vst[z] 
= 1;
            re3(i, LL[z], RR[z]) {
                ff 
= 1; re(j, len[i]) {
                    x0 
= x + PX[i][j]; y0 = y + PY[i][j];
                    
if (x0 < 0 || x0 >= S || y0 < 0 || y0 >= S || x0 < y0 || a[x0][y0] != a[x][y]) {ff = 0break;}
                }
                
if (ff) {
                    _x 
= _pos[i][x][y]; rh = rowh[_x]; delcol(d[rh].c);
                    
for (int j=d[rh].R; j != rh; j=d[j].R) delcol(d[j].c);
                    
break;
                }
            }
        }
    }
}
bool dfs(int dep)
{
    
if (!d[0].R) {res_len = dep; return 1;}
    
int mins = INF, c0; for (int i=d[0].R; i; i=d[i].R) if (!cols[i]) return 0else if (cols[i] < mins) {mins = cols[i]; c0 = i;}
    delcol(c0);
    
for (int i=d[c0].D; i != c0; i=d[i].D) {
        
for (int j=d[i].R; j != i; j=d[j].R) {delcol(d[j].c);}
        res[dep] 
= d[i].r; if (dfs(dep + 1)) return 1;
        
for (int j=d[i].L; j != i; j=d[j].L) resucol(d[j].c);
    }
    resucol(c0);
    
return 0;
}
void solve()
{
    
int x, y, z;
    
if (dfs(0)) {
        re(i, res_len) {
            z 
= pos[res[i]][0]; x = pos[res[i]][1]; y = pos[res[i]][2];
            re(j, len[z]) a[x 
+ PX[z][j]][y + PY[z][j]] = SSS[z];
        }
    } 
else res_len = -1;
}
void pri()
{
    freopen(
"zhzyx.out""w", stdout);
    
if (res_len == -1) puts("No solution"); else re(i, S) {re(j, i+1) putchar(a[i][j]); puts("");}
    fclose(stdout);
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}

Feedback

# re: NOI2005 智慧珠游戏  回复  更多评论   

2014-09-28 17:01 by
把代码放在vs2013上跑,一直在prepare里循环...

# re: NOI2005 智慧珠游戏  回复  更多评论   

2015-01-07 18:40 by sluqy671
add_node(No0, 55 + SSS[i] - 64);
请问这句话有什么作用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理