http://acm.sgu.ru/problem.php?contest=0&problem=433题目大意：要求使用一个长为L，宽为1的矩形，刚好填充一个大的矩形。 解法：比较裸的DLX，knuth的论文中有更加复杂的图案。 建图：行代表 以一个格子为起点，使用第i个小矩形，横着或者竖着填充大矩形。 列代表 每个格子。
  sgu_433
1 // 返回一组解，不是最优解
2#include <stdio.h>
3#include <memory.h>
4#include <iostream>
5#include <cstring>
6using namespace std;
7
8int dx[ ] =  { -1, 0, 0, 1 };
9int dy[ ] = { 0, -1, 1, 0 };
10
11const int maxn = 1010;
12const int maxm = 105;
13const int maxt = maxn * maxm;
14
15int S[ maxm ], O[ maxn ]; // S[] 列链表中结点的总数 O[] 记录搜索结果
16int L[ maxt ], R[ maxt ], U[ maxt ], D[ maxt ]; // 四个方向
17int C[ maxt ], W[ maxt ]; // C[]列指针头 W[]行指针头
18int mat[maxn][maxm]; // 稀疏矩阵
19int ANS, CNT;
20
21void build( int n, int m ) // 邻接矩阵的build函数
22{
23 int i, j, tot = m, first;
24 R[0] = 1; L[0] = m;
25 for( i = 1; i <= m; i++ )
26  {
27 L[i] = i - 1; R[i] = ( i + 1 ) % ( m + 1 );
28 U[i] = D[i] = C[i] = i; S[i] = 0;
29 }
30 for( i = 1; i <= n; i++ )
31 {
32 first = 0;
33 for( j = 1; j <= m; j++ )if( mat[i][j] )
34 {
35 tot++;
36 U[tot] = U[j]; D[tot] = j;
37 D[U[j]] = tot; U[j] = tot;
38 if( first == 0 ) first = L[tot] = R[tot] = tot;
39 else
40 {
41 L[tot] = L[first]; R[tot] = first;
42 R[L[first]] = tot; L[first] = tot;
43 }
44 W[tot] = i; C[tot] = j; S[j]++;
45 }
46 }
47 }
48
49void remove( int c )
50{
51 int i, j;
52 //remove column c and all row i that A[i][c] == 1
53 L[R[c]] = L[c];
54 R[L[c]] = R[c];
55 //remove column c;
56 for( i = D[c]; i != c; i = D[i] )
57 {
58 //remove i that A[i][c] == 1
59 for( j = R[i]; j != i; j = R[j] )
60 {
61 U[D[j]] = U[j];
62 D[U[j]] = D[j];
63 S[C[j]]--;
64 //decrease the count of column C[j];
65 }
66 }
67}
68
69void resume( int c )
70{
71 int i, j;
72 for( i = U[c]; i != c; i = U[i] )
73 {
74 for( j = L[i]; j != i; j = L[j] )
75 {
76 S[C[j]]++;
77 U[D[j]] = j;
78 D[U[j]] = j;
79 }
80 }
81 L[R[c]] = c;
82 R[L[c]] = c;
83}
84
85int dfs( int k )
86{
87 CNT++;
88 if( CNT > 10000 ) return 0;
89 int i, j, t, m = maxm, mn;
90 if( R[0] == 0 )
91 {
92 //One of the answers has been found.
93 ANS = k;
94 return 1;
95 }
96 for( t = R[0]; t != 0; t = R[t] )
97 if( S[t] < m ) { m = S[t]; mn = t; }
98 remove( mn );
99 for( i = D[mn]; i != mn; i = D[i] )
100 {
101 O[k] = i;//record the answer.
102 for( j = R[i]; j != i; j = R[j] )
103 remove( C[j] );
104 if( dfs( k + 1 ) ) return 1;
105 for( j = L[i]; j != i; j = L[j] )
106 resume( C[j] );
107 }
108 resume( mn );
109 return 0;
110}
111
112int l[ 10 ];
113int ch[ 25 ][ 25 ];
114int vis[ 10 ];
115char col[ 30 ];
116
117int main( )
118{
119 //freopen("out.out","w",stdout);
120 int n, m, k, i, j, c;
121 for( int i = 1; i <= 26; i++ )
122 col[ i ] = i + 'a' - 1;
123 while( scanf("%d%d%d",&n,&m,&k) != EOF )
124 {
125 for( int i = 0; i < k; i++ )
126 scanf("%d",&l[ i ]);
127 memset( mat, 0, sizeof( mat ) );
128 int q = 1;
129 for( int i = 0; i < n; i++ )
130 {
131 for( int j = 0; j < m; j++ )
132 {
133 for( int p = 0; p < k; p++ )
134 {
135 if( j + l[ p ] <= m ) // 横着
136 for( int x = 0; x < l[ p ]; x++ )
137 mat[ q ][ i * m + j + x + 1 ] = 1;
138 q++;
139 if( i + l[ p ] <= n ) // 竖着
140 for( int x = 0; x < l[ p ]; x++ )
141 mat[ q ][ ( i + x ) * m + j + 1 ] = 1;
142 q++;
143 }
144 }
145 }
146 build( q - 1, n * m );
147 CNT = 0;
148 int z, x, y, u, v, xx, yy;
149 if( dfs( 0 ) == 0 ) puts("NO");
150 else
151 {
152 printf("YES\n");
153 memset( ch, 0, sizeof( ch ) );
154 for( int i = 0; i < ANS; i++ )
155 {
156 z = W[ O[ i ] ] - 1;
157 x = z / ( 2 * k ) / m;
158 y = z / ( 2 * k ) % m;
159 u = z % ( 2 * k ) / 2; // 矩形类型
160 v = z % 2; // 横or竖
161 memset( vis, 0, sizeof( vis ) );
162 int j;
163 if( !v ) // 横着
164 {
165 for( int p = 0; p < l[ u ]; p++ )
166 {
167 for( j = 0; j < 4; j++ )
168 {
169 xx = x + dx[ j ], yy = y + p + dy[ j ];
170 if( xx < n && xx >= 0 && yy < m && yy >= 0 )
171 vis[ ch[ xx ][ yy ] ] = 1;
172 }
173 }
174 for( j = 1; ; j++ ) if( !vis[ j ] ) break;
175
176 for( int p = 0; p < l[ u ]; p++ ) ch[ x ][ p + y ] = j;
177 }
178
179 else // 竖着
180 {
181 for( int p = 0; p < l[ u ]; p++ )
182 {
183 for( j = 0; j < 4; j++ )
184 {
185 xx = x + p + dx[ j ], yy = y + dy[ j ];
186 if( xx < n && xx >= 0 && yy < m && yy >= 0 )
187 vis[ ch[ xx ][ yy ] ] = 1;
188 }
189 }
190 for( j = 1; ; j++ ) if( !vis[ j ] ) break;
191
192 for( int p = 0; p < l[ u ]; p++ ) ch[ p + x ][ y ] = j;
193 }
194 }
195 for( int i = 0; i < n; i++ )
196 {
197 for( int j = 0; j < m; j++ )
198 printf("%c",col[ ch[ i ][ j ] ]);
199 printf("\n");
200 }
201 }
202 }
203 return 0;
204}
205
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 31 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | 14 | 15 | 16 | 17 | 18 | 19 | 20 | | 21 | 22 | 23 | 24 | 25 | 26 | 27 | | 28 | 29 | 30 | 31 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
常用链接
留言簿
随笔分类
随笔档案
传送门
搜索
最新评论
阅读排行榜
评论排行榜
|
|