HDU 1426 dancing links 수 독 문제 해결

제목 의 대의:
이것 은 가장 간단 한 수 독 충전 문제 로 제목 은 하나의 수 독 만 생 길 수 있 기 때문에 이곳 의 초기 9 궁 격 은 비교적 조밀 하고 직접 dfs 도 문제 가 없다.
근 데 요즘 춤 연습 하고 있어 요. 링크 스, 이런 데이터 구조 해결 은 의심 할 여지없이 효율 이 매우 높 을 것 이다
dancing links 의 수 독 제한 조건 은:
1. 줄 당 9 개의 원소, 총 9 줄 대응 dlx 81 열
2. 각 열 에 9 개의 요소 가 있 고 모두 9 줄 입 니 다. 대응 dlx 81 열
3. 각 구 궁 칸 당 9 개의 원소 가 있 으 며, 총 9 줄 대응 dlx 81 열
4.81 칸, 칸 당 최대 한 칸
 

  1 #include <iostream>

  2 #include <cstring>

  3 #include <cstdio>

  4 #include <algorithm>

  5 #include <queue>

  6 #include <climits>

  7 #include <cmath>

  8 

  9 using namespace std;

 10 #define N 1000

 11 #define MAXNODE 1000000

 12 const int INF = INT_MAX;

 13 const double eps = 1e-8;

 14 

 15 int a[10][10];

 16 char str[5];

 17 

 18 int belong[9][9] =  {

 19                         {1,1,1,2,2,2,3,3,3},

 20                         {1,1,1,2,2,2,3,3,3},

 21                         {1,1,1,2,2,2,3,3,3},

 22                         {4,4,4,5,5,5,6,6,6},

 23                         {4,4,4,5,5,5,6,6,6},

 24                         {4,4,4,5,5,5,6,6,6},

 25                         {7,7,7,8,8,8,9,9,9},

 26                         {7,7,7,8,8,8,9,9,9},

 27                         {7,7,7,8,8,8,9,9,9},

 28                     };

 29 struct DLX{

 30     int n ,m , size;

 31     int col[MAXNODE] , row[MAXNODE];

 32     int U[MAXNODE] , D[MAXNODE] , L[MAXNODE] , R[MAXNODE];

 33     int cnt_col[N] , first[N];

 34     int ans[100];

 35 

 36     void init(int _n , int _m)

 37     {

 38         n = _n , m = _m;

 39         size= m ;

 40         for(int i=0 ; i<=m ; i++){

 41             L[i] = i-1 , R[i] = i+1;

 42             U[i] = D[i] = i;

 43         }

 44         L[0] = m , R[m] = 0;

 45         for(int i=1 ; i<=m ; i++) cnt_col[i] = 0;

 46         for(int i=1 ; i<=n ; i++) first[i] = -1;

 47     }

 48 

 49     void link(int r , int c)

 50     {

 51         ++size;

 52         U[D[c]] = size , D[size] = D[c];

 53         U[size] = c , D[c] = size;

 54 

 55         if(first[r]<0) L[size]=R[size]=first[r] = size;

 56         else{

 57             L[R[first[r]]] = size , R[size] = R[first[r]];

 58             L[size] = first[r] , R[first[r]] = size;

 59         }

 60         row[size] = r , col[size] = c , cnt_col[c]++;

 61     }

 62 

 63     void Remove(int c)

 64     {

 65         L[R[c]] = L[c] , R[L[c]] = R[c];

 66         for(int i=D[c] ; i!=c ; i=D[i]){

 67             for(int j=R[i] ; j!=i ; j=R[j]){

 68                 U[D[j]] = U[j] , D[U[j]] = D[j];

 69                 cnt_col[col[j]]--;

 70             }

 71         }

 72     }

 73 

 74     void Resume(int c)

 75     {

 76         for(int i=U[c] ; i!=c ; i=U[i]){

 77             for(int j=L[i] ; j!=i ; j=L[j]){

 78                 U[D[j]] = D[U[j]] = j;

 79                 cnt_col[col[j]]++;

 80             }

 81         }

 82         L[R[c]] = R[L[c]] = c;

 83     }

 84 

 85     bool Dance(int d)

 86     {

 87         if(!R[0]){

 88             for(int i=0 ; i<d ; i++){

 89                     int r = (ans[i]-1)/81;

 90                     int c = ((ans[i]-1)%81)/9;

 91                     a[r][c] = ((ans[i]-1)%9)+1;

 92             }

 93             return true;

 94         }

 95         int st=R[0];

 96         for(int i=R[0] ; i!=0 ; i=R[i])

 97             if(cnt_col[i]<cnt_col[st])

 98                 st = i;

 99         Remove(st);

100         for(int i=D[st] ; i!=st ; i=D[i]){

101             ans[d] = row[i];

102             for(int j=R[i] ; j!=i ; j=R[j]) Remove(col[j]);

103             if(Dance(d+1)) return true;

104             for(int j=L[i] ; j!=i ; j=L[j]) Resume(col[j]);

105         }

106         Resume(st);

107         return false;

108     }

109 

110 }dlx;

111 

112 void printM()

113 {

114     for(int i=0 ; i<9 ; i++)

115         for(int j=0 ; j<9 ; j++){

116            if(j<8) printf("%d " , a[i][j]);

117            else printf("%d
" , a[i][j]);

118         }

119 }

120 

121 int main()

122 {

123   //  freopen("a.in" , "r" , stdin);

124     int index=0;

125     bool flag = false;

126     while(~scanf("%s" , str))

127     {

128         if(flag) puts("");

129         flag = true;

130         if(str[0] == '?') a[index/9][index%9] = 0;

131         else a[index/9][index%9] = str[0]-'0';

132         index++;

133         while(index<81){

134             scanf("%s" , str);

135             if(str[0] == '?') a[index/9][index%9] = 0;

136             else a[index/9][index%9] = str[0]-'0';

137             index++;

138         }

139        // printM();

140         dlx.init(729 , 324);

141         for(int i=0 ; i<9 ; i++)

142             for(int j=0 ; j<9 ; j++)

143             {

144                 if(a[i][j]){

145                     dlx.link((i*9+j)*9+a[i][j] , i*9+a[i][j]);

146                     dlx.link((i*9+j)*9+a[i][j] , 81+j*9+a[i][j]);

147                     dlx.link((i*9+j)*9+a[i][j] , 162+(belong[i][j]-1)*9+a[i][j]);

148                     dlx.link((i*9+j)*9+a[i][j] , 243+i*9+j+1);

149                 }

150                 else{

151                     for(int k=1 ; k<=9 ; k++){

152                         dlx.link((i*9+j)*9+k , i*9+k);

153                         dlx.link((i*9+j)*9+k , 81+j*9+k);

154                         dlx.link((i*9+j)*9+k , 162+(belong[i][j]-1)*9+k);

155                         dlx.link((i*9+j)*9+k , 243+i*9+j+1);

156                     }

157                 }

158             }

159         dlx.Dance(0);

160 

161         printM();

162         index=0;

163     }

164 

165     return 0;

166 }