#include <stdio.h>
#include <ctime>
#include <stdlib.h>
#include <string.h>
const int SIZE = 16;
const int N = SIZE*SIZE*SIZE;
const int M = SIZE*SIZE*4;
const char LET = 'A';
char map[SIZE+1][SIZE+1];
int L[N*M+1], R[N*M+1], U[N*M+1], D[N*M+1], Sum[N*M+1];
int x[5], lenx;
int Row[N*M+1], Col[N*M+1];
int ans[N+1], anslen;
int id;
bool OK;
void pre() {
for(int i = 0; i <= M; i ++) {
L[i] = i - 1;
R[i] = i + 1;
U[i] = D[i] = i;
Sum[i] = 0;
}
L[0] = M; R[M] = 0;
id = M + 1;
}
inline void insert(int i, int *xx) {
for(int j = 0; j < lenx; j ++, id ++) {
int x = xx[j]+1;
Row[id] = i;
Col[id] = x;
Sum[x] ++;
U[id] = x;
D[id] = D[x];
U[D[x]] = id;
D[x] = id;
if( j == 0 ) {
L[id] = R[id] = id;
} else {
L[id] = id - 1;
R[id] = id - j;
R[id-1] = id;
L[id-j] = id;
}
}
}
void build() {
for(int i = 0; i < SIZE; i ++) {
for(int j = 0; j < SIZE; j ++) {
for(int k = 0; k < SIZE; k ++) {
int row = k+SIZE*j+SIZE*SIZE*i+1;
lenx = 0;
if( map[i][j] == '-' || map[i][j] == k + 'A' ) {
x[lenx++] = SIZE*i + k;
x[lenx++] = SIZE*SIZE + SIZE*j + k;
int temp = (i / 4) * 4 + j / 4;
x[lenx++] = 2*SIZE*SIZE + temp * SIZE + k;
x[lenx++] = 3*SIZE*SIZE + i*SIZE + j;
insert(row, x);
}
}
}
}
}
inline void remove(int c) {
R[L[c]] = R[c];
L[R[c]] = L[c];
for(int id = D[c]; id != c; id = D[id]) {
for(int i = R[id]; i != id; i = R[i] ) {
D[U[i]] = D[i];
U[D[i]] = U[i];
Sum[Col[i]] --;
}
}
}
inline void resume(int c) {
L[R[c]] = c;
R[L[c]] = c;
for(int id = D[c]; id != c; id = D[id]) {
for(int i = R[id]; i != id; i = R[i] ) {
U[D[i]] = i;
D[U[i]] = i;
Sum[Col[i]] ++;
}
}
}
bool dfs(int deep) {
if( R[0] == 0 ) return true;
int column = R[0];
for(int i = R[0]; i != 0; i = R[i]) {
if( Sum[i] < Sum[column] ) {
column = i;
if( Sum[column] < 2 ) break;
}
}
remove(column);
for(int id = D[column]; id != column; id = D[id]) {
ans[deep] = Row[id];
for(int i = R[id]; i != id; i = R[i]) remove(Col[i]);
if( dfs( deep + 1) ) return true;
for(int i = L[id]; i != id; i = L[i]) resume(Col[i]);
}
resume(column);
return false;
}
int main() {
freopen("in.txt","r",stdin);
while( scanf("%s", map[0]) != EOF ) {
for(int i = 1; i < SIZE; i ++) scanf("%s", map[i]);
pre();
build();
dfs(0);
for(int i = 0; i < 256; i ++) {
int r = (ans[i] - 1) / SIZE / SIZE % SIZE;
int c = (ans[i] - 1) / SIZE % SIZE;
int val = (ans[i] - 1) % SIZE;
map[r][c] = val + 'A';
}
for(int i = 0; i < SIZE; i ++){
for(int j = 0; j < SIZE; j ++) printf("%c",map[i][j]);
printf("\n");
}
printf("\n");
}
while(1);
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=3076