【POJ】3076 Sudoku

  1 #include<cstdio>
  2 #include<cstring>
  3 #define INF 0x7FFFFFFF
  4 #define MAXS 16
  5 #define MAXH 4100
  6 #define MAXL 1025
  7 #define MAXN 4200000
  8 char sd[MAXS][MAXS];
  9 int L[MAXN], R[MAXN], U[MAXN], D[MAXN], C[MAXN], X[MAXN];
 10 int size, S[MAXL], H[MAXH], Q[MAXH];
 11 bool vis[MAXH];
 12 bool Read()
 13 {
 14     int i, j;
 15     for (i = 0; i < MAXS; i++)
 16     {
 17         for (j = 0; j < MAXS; j++)
 18         {
 19             if (scanf(" %c", &sd[i][j]) == EOF)
 20                 return false;
 21         }
 22     }
 23     return true;
 24 }
 25 void Init()
 26 {
 27     int i;
 28     for (i = 0; i < MAXL; i++)
 29     {
 30         R[i] = i + 1;
 31         L[i + 1] = i;
 32         U[i] = D[i] = i;
 33         S[i] = 0;
 34     }
 35     R[MAXL - 1] = 0;
 36     size = MAXL;
 37 }
 38 void Remove(int c)
 39 {
 40     int i, j;
 41     L[R[c]] = L[c];
 42     R[L[c]] = R[c];
 43     for (i = D[c]; i != c; i = D[i])
 44     {
 45         for (j = R[i]; j != i; j = R[j])
 46         {
 47             U[D[j]] = U[j];
 48             D[U[j]] = D[j];
 49             S[C[j]]--;
 50         }
 51     }
 52 }
 53 void Resume(int c)
 54 {
 55     int i, j;
 56     L[R[c]] = c;
 57     R[L[c]] = c;
 58     for (i = D[c]; i != c; i = D[i])
 59     {
 60         for (j = R[i]; j != i; j = R[j])
 61         {
 62             U[D[j]] = j;
 63             D[U[j]] = j;
 64             S[C[j]]++;
 65         }
 66     }
 67 }
 68 inline void Link(int r, int c)
 69 {
 70     D[size] = D[c];
 71     U[size] = c;
 72     U[D[c]] = size;
 73     D[c] = size;
 74     if (H[r] < 0)
 75         H[r] = L[size] = R[size] = size;
 76     else
 77     {
 78         L[size] = H[r];
 79         R[size] = R[H[r]];
 80         L[R[H[r]]] = size;
 81         R[H[r]] = size;
 82     }
 83     S[c]++;
 84     X[size] = r;
 85     C[size++] = c;
 86 }
 87 bool Dance()
 88 {
 89     if (R[0] == 0)
 90         return true;
 91     int i, j, temp, c;
 92     for (temp = INF,i = R[0]; i; i = R[i])
 93     {
 94         if (temp > S[i])
 95         {
 96             temp = S[i];
 97             c = i;
 98         }
 99     }
100     Remove(c);
101     for (i = D[c]; i != c; i = D[i])
102     {
103         vis[X[i]] = true;
104         for (j = R[i]; j != i; j = R[j])
105             Remove(C[j]);
106         if (Dance())
107             return true;
108         for (j = L[i]; j != i; j = L[j])
109             Resume(C[j]);
110         vis[X[i]] = false;
111     }
112     Resume(c);
113     return false;
114 }
115 int main()
116 {
117     int i, j, k, r;
118     while (Read())
119     {
120         Init();
121         for (i = r = 0; i < MAXS; i++)
122         {
123             for (j = 0; j < MAXS; j++)
124             {
125                 if (sd[i][j] == '-')
126                 {
127                     for (k = 0; k < MAXS; k++)
128                     {
129                         H[++r] = -1;
130                         Q[r] = k;
131                         Link(r, (i << 4) + k + 1);
132                         Link(r, 256 + (j << 4) + k + 1);
133                         Link(r,    512 + ((((i >> 2) << 2) + (j >> 2)) << 4) + k + 1);
134                         Link(r, 768 + (i << 4) + j + 1);
135                     }
136                 }
137                 else
138                 {
139                     k = sd[i][j] - 'A';
140                     H[++r] = -1;
141                     Q[r] = k;
142                     Link(r, (i << 4) + k + 1);
143                     Link(r, 256 + (j << 4) + k + 1);
144                     Link(r, 512 + ((((i >> 2) << 2) + (j >> 2)) << 4) + k + 1);
145                     Link(r, 768 + (i << 4) + j + 1);
146                 }
147             }
148         }
149         memset(vis, false, sizeof(vis));
150         Dance();
151         for (k = 0, i = 1; i <= r; i++)
152         {
153             if (vis[i])
154             {
155                 k++;
156                 putchar('A' + Q[i]);
157                 if (k % 16 == 0)
158                     putchar('\n');
159             }
160         }
161         putchar('\n');
162     }
163     return 0;
164 }