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
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
26 | 27 | 28 | 29 | 30 | 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 |
|
常用链接
留言簿
随笔分类
随笔档案
传送门
搜索
最新评论
阅读排行榜
评论排行榜
|
|