模型转换之最小可重复覆盖（Dancing Links）~
View Code
1 #include <cstdio>
2 #include <cstring>
3
4 using namespace std;
5
6 const int SIZE = 16;
7 const int MAXR = 256;
8 const int MAXC = 32;
9 const int INF = (1 << 20);
10 const int dx[] = {-1,0,1,0};
11 const int dy[] = {0,1,0,-1};
12
13 struct Node
14 {
15 Node * u;
16 Node * d;
17 Node * l;
18 Node * r;
19 int rnum;
20 int cnum;
21 };
22
23 int node;
24 int sum[MAXC];
25 Node head;
26 Node row[MAXR];
27 Node column[MAXC];
28 Node pool[MAXR * MAXC];
29
30 //int alen;
31 //int ans[MAXR];
32
33 int hi;
34 int wi;
35 char board[SIZE][SIZE];
36 int tag[SIZE][SIZE];
37
38 int maxstep;
39
40 bool covered[MAXC];
41
42 void InitDLX(int nr,int nc)
43 {
44 node = 0;
45 memset(sum,0,sizeof(sum));
46 head.r = &column[0];
47 column[0].cnum = 0;
48 column[0].l = &head;
49 column[0].u = column[0].d = &column[0];
50 for (int i = 1;i < nc;i++)
51 {
52 column[i].cnum = i;
53 column[i-1].r = &column[i];
54 column[i].l = &column[i-1];
55 column[i].u = column[i].d = &column[i];
56 }
57 column[nc-1].r = &head;
58 head.l = &column[nc-1];
59
60 for (int i = 0;i < nr;i++)
61 row[i].l = row[i].r = &row[i];
62 }
63
64 void InsertDLX(int r,int c)
65 {
66 sum[c]++;
67 pool[node].rnum = r;
68 pool[node].cnum = c;
69 pool[node].l = row[r].l;
70 pool[node].r = &row[r];
71 row[r].l->r = &pool[node];
72 row[r].l = &pool[node];
73 pool[node].u = column[c].u;
74 pool[node].d = &column[c];
75 column[c].u->d = &pool[node];
76 column[c].u = &pool[node];
77
78 node++;
79 }
80
81 void DeleteRowHeadDLX(int nr)
82 {
83 for (int i = 0;i < nr;i++)
84 {
85 row[i].l->r = row[i].r;
86 row[i].r->l = row[i].l;
87 }
88 }
89
90 void RemoveColumn(Node * col)
91 {
92 for (Node * p = col->d;p != col;p = p->d)
93 {
94 p->r->l = p->l;
95 p->l->r = p->r;
96 sum[p->cnum]--;
97 }
98 }
99
100 void ResumeColumn(Node * col)
101 {
102 for (Node * p = col->d;p != col;p = p->d)
103 {
104 p->r->l = p;
105 p->l->r = p;
106 sum[p->cnum]++;
107 }
108 }
109
110 int Estimate()
111 {
112 int value = 0;
113 memset(covered,false,sizeof(covered));
114 for (Node * p = head.r;p != & head;p = p->r)
115 if (!covered[p->cnum])
116 {
117 covered[p->cnum] = true;
118 value++;
119 bool can = false;
120 for (Node * q = p->d;q != p;q = q->d)
121 {
122 can = true;
123 for (Node * o = q->r;o != q;o = o->r)
124 covered[o->cnum] = true;
125 }
126 if (!can) return INF;
127 }
128 return value;
129 }
130
131 bool dfs(int k)
132 {
133 if (k + Estimate() > maxstep) return false;
134
135 if (head.r == &head)
136 {
137 //alen = k;
138 return true;
139 }
140
141 int minl = INF;
142 Node * mincol;
143 for (Node * p = head.r;p != &head;p = p->r)
144 if (sum[p->cnum] < minl)
145 {
146 minl = sum[p->cnum];
147 mincol = p;
148 }
149 for (Node * p = mincol->d;p != mincol;p = p->d)
150 {
151 RemoveColumn(p);
152 for (Node * q = p->r;q != p;q = q->r)
153 RemoveColumn(q);
154 if (dfs(k + 1))
155 {
156 //ans[k] = p->rnum + 1;
157 return true;
158 }
159 for (Node * q = p->l;q != p;q = q->l)
160 ResumeColumn(q);
161 ResumeColumn(p);
162 }
163 return false;
164 }
165
166 bool legal(int x,int y)
167 {
168 return x >= 0 && x < hi && y >= 0 && y < wi && board[x][y] == '.';
169 }
170
171 int main()
172 {
173 while(scanf("%d %d",&hi,&wi) != EOF)
174 {
175 int scnt = 0;
176 int wcnt = 0;
177 memset(tag,-1,sizeof(tag));
178
179 for(int i = 0;i < hi;i++)
180 {
181 scanf("%s",board[i]);
182 for(int j = 0;j < wi;j++)
183 if(board[i][j] == '.')
184 tag[i][j] = scnt++;
185 else if(board[i][j] == '#')
186 tag[i][j] = wcnt++;
187 }
188
189 InitDLX(scnt,wcnt);
190
191 for(int i = 0;i < hi;i++)
192 for(int j = 0;j < wi;j++)
193 if(board[i][j] == '#')
194 for(int k = 0;k < 4;k++)
195 {
196 int x = i + dx[k];
197 int y = j + dy[k];
198 while(legal(x,y))
199 {
200 InsertDLX(tag[x][y],tag[i][j]);
201 x += dx[k];
202 y += dy[k];
203 }
204 }
205
206 DeleteRowHeadDLX(scnt);
207
208 for(maxstep = 0;!dfs(0);maxstep++) ;
209
210 printf("%d\n",maxstep);
211 }
212 return 0;
213 }