1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <cmath>  6 #include <algorithm>  7 #include <string>  8 #include <queue>  9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <cctype> 15 #include <time.h> 16  17 using namespace std; 18  19 const int INF = 1<<30; 20 const int MAXN = 1055; 21 const int MAXNODE = 16555; 22 const int MAXR = 1055; 23  24 struct DLX { 25 // 行编号从1开始，列编号为1~n，结点0是表头结点；结点1~n是各列顶部的虚拟结点 26     int n, sz; // 列数，结点总数 27     int S[MAXN]; //各列结点数 28  29     int row[MAXNODE], col[MAXNODE]; //各结点行列编号 30     int L[MAXNODE], R[MAXNODE], U[MAXNODE], D[MAXNODE]; //十字链表 31  32     int ansd, ans[MAXR]; // 解 33  34     void init(int n)  { //n是列数 35         this->n = n; 36  37         //虚拟结点 38         for (int i = 0; i <= n; i++) { 39             U[i] = i; D[i] = i; L[i] = i-1; R[i] = i+1; 40         } 41         R[n] = 0; L[0] = n; 42         sz = n+1; 43         memset(S, 0, sizeof(S)); 44     } 45  46     void addRow(int r, vector<int> columns) { 47         //这一行的第一个结点 48         //行没有设头结点，每一行连成一个环形 49         int first = sz; 50         for (int i = 0; i < columns.size(); i++) { 51             int c = columns[i]; 52             L[sz] = sz-1; R[sz] = sz+1; D[sz] = c; U[sz] = U[c]; 53             D[U[c]] = sz; U[c] = sz; 54             row[sz] = r; col[sz] = c; 55             S[c]++; sz++; 56         } 57         R[sz-1] = first; L[first] = sz-1; 58     } 59  60     //顺着链表A，遍历s外的其他元素 61     #define FOR(i, A, s) for (int i = A[s]; i != s; i = A[i]) 62  63     void remove(int c) { //删除c列 64         L[R[c]] = L[c]; R[L[c]] = R[c]; 65         for (int i = D[c]; i != c; i = D[i]) // 对于每一个c列不为0的所有行 66             for (int j = R[i]; j != i; j = R[j]) { //删除这一整行 67                 U[D[j]] = U[j]; D[U[j]] = D[j]; S[col[j]]--; 68             } 69     } 70  71     void restore(int c) { //回连c列 72         for (int i = U[c]; i != c; i = U[i]) 73             for (int j = L[i]; j != i; j = L[j]) { 74                 U[D[j]] = j; D[U[j]] = j; S[col[j]]++; 75             } 76         L[R[c]] = c; R[L[c]] = c; 77     } 78  79     bool dfs(int d) { //d为递归深度 80         if (R[0] == 0) { //找到解 81             ansd = d; //记录解的长度 82             return true; 83         } 84  85         //找S最小的C列 86         int c = R[0]; //第一个未删除的列 87         for (int i = R[0]; i != 0; i = R[i]) if (S[i]<S[c]) c = i; 88  89         remove(c); //删除第c列 90         for (int i = D[c]; i != c; i = D[i]) { //用结点i所在的行覆盖第c列 91             ans[d] = row[i]; 92             for (int j = R[i]; j != i; j = R[j]) remove(col[j]); //删除节结点i所在行覆盖第c列 93             if (dfs(d+1)) return true; 94             for (int j = L[i]; j != i; j = L[j]) restore(col[j]); // 恢复 95         } 96         restore(c); //恢复 97         return false; 98     } 99 100     bool solve(vector<int> &v) {101         v.clear();102         if(!dfs(0)) return false;103         for (int i = 0; i < ansd; i++) v.push_back(ans[i]);104         return true;105     }106 };107 108 const int SLOT = 0;109 const int ROW = 1;110 const int COL = 2;111 const int SUB = 3;112 113 inline int encode(int a, int b, int c) {114     return a*256 + b*16 + c + 1;115 }116 117 inline void decode(int code, int &a, int &b, int &c) {118     code--;119     c = code%16; code /= 16;120     b = code%16; code /= 16;121     a = code;122 }123 124 char puzzle[16][20];125 126 bool read() {127     for (int i = 0; i < 16; i++)128         if (scanf("%s", puzzle[i])!=1) return false;129     return true;130 }131 132 DLX solver;133 134 int main() {135     #ifdef Phantom01136         freopen("LA2659.txt", "r", stdin);137     #endif //Phantom01138 139     int T= 0;140 141     while (read()) {142         if (T!=0) puts(""); T++;143         solver.init(1024);144         for (int r = 0; r < 16; r++)145             for (int c = 0; c < 16; c++)146                 for (int v = 0; v < 16; v++)147                     if (puzzle[r][c]==‘-‘|| puzzle[r][c]==‘A‘+v) {148                         vector<int> columns;149                         columns.push_back(encode(SLOT, r, c));150                         columns.push_back(encode(ROW, r, v));151                         columns.push_back(encode(COL, c, v));152                         columns.push_back(encode(SUB, (r/4)*4+c/4, v));153                         solver.addRow(encode(r, c, v), columns);154                     }155         vector<int> ans;156         if (!solver.solve(ans)) while (1) ;157 158         for (int i = 0; i < ans.size(); i++) {159             int r, c, v;160             decode(ans[i], r, c, v);161             puzzle[r][c] = ‘A‘+v;162         }163         for (int i = 0; i < 16; i++) {164             printf("%s\n", puzzle[i]);165         }166     }167 168     return 0;169 }