C++(g++ 7.5.0) 解法, 执行用时: 114ms, 内存消耗: 824K, 提交时间: 2023-02-05 11:03:47

//#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

const int N = 4;
int p2n[1<<(N*N)], pop_cnt[1<<(N*N)];

inline int lowbit(int x) {
	return x & -x;
}

inline void draw(int row, int col, int num, char (*ans)[N*N], int (*can)[N*N]) {
	ans[row][col] = num + 'A';
	for (int i = 0; i < N*N; ++i) {
		can[i][col] &= ~(1 << num);
		can[row][i] &= ~(1 << num);
	}
	for (int i = row / N * N; i < row / N * N + N; ++i) {
		for (int j = col / N * N; j < col / N * N + N; ++j) can[i][j] &= ~(1 << num);
	}
	can[row][col] = 1 << num;
}

inline void print(const char (*ans)[N*N]) {
	for (int i = 0; i < N*N; ++i) {
		for (int j = 0; j < N*N; ++j) cout << ans[i][j];
		cout << "\n";
	}
}

bool dfs(int rest, char (*ans)[N*N], int (*can)[N*N]) {
	if (!rest) {
		print(ans);
		return true;
	}

	// cut 1 0-remove
	for (int i = 0; i < N*N; ++i)
		for (int j = 0; j < N*N; ++j)
			if (ans[i][j] == '-' && can[i][j] == 0) return false;
	
	// cut 2 1-fill
	for (int i = 0; i < N*N; ++i)
		for (int j = 0; j < N*N; ++j)
			if (ans[i][j] == '-' && pop_cnt[can[i][j]] == 1) {
				--rest;
				draw(i, j, p2n[lowbit(can[i][j])], ans, can);
			}
	
	// cut 3 row-all
	for (int i = 0; i < N*N; ++i) {
		int all = 0, drawn = 0, only = (1 << (N*N)) - 1;
		for (int j = 0; j < N*N; ++j) {
			only &= ~(all & can[i][j]);
			all |= can[i][j];
			if (ans[i][j] != '-') drawn |= can[i][j];
		}
		if (all != (1 << (N*N)) - 1) return false;
		only &= ~drawn;
		for ( ; only; only -= lowbit(only)) {
			int num = p2n[lowbit(only)];
			for (int j = 0; j < N*N; ++j)
				if (can[i][j] & (1 << num)) {
					--rest;
					draw(i, j, num, ans, can);
					break;
				}
		}
	}
	
	// cut 4 col-all
	for (int i = 0; i < N*N; ++i) {
		int all = 0, drawn = 0, only = (1 << (N*N)) - 1;
		for (int j = 0; j < N*N; ++j) {
			only &= ~(all & can[j][i]);
			all |= can[j][i];
			if (ans[j][i] != '-') drawn |= can[j][i];
		}
		if (all != (1 << (N*N)) - 1) return false;
		only &= ~drawn;
		for ( ; only; only -= lowbit(only)) {
			int num = p2n[lowbit(only)];
			for (int j = 0; j < N*N; ++j)
				if (can[j][i] & (1 << num)) {
					--rest;
					draw(j, i, num, ans, can);
					break;
				}
		}
	}
	
	// cut 5 blk-all
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int all = 0, only = (1 << (N*N)) - 1, drawn = 0;
			for (int k = 0; k < N; ++k) {
				for (int l = 0; l < N; ++l) {
					only &= ~(all & can[N*i+k][N*j+l]);
					all |= can[N*i+k][N*j+l];
					if (ans[N*i+k][N*j+l] != '-') drawn |= can[N*i+k][N*j+l];
				}
			}
			if (all != (1 << (N*N)) - 1) return false;
			only &= ~drawn;
			for ( ; only; only -= lowbit(only)) {
				int num = p2n[lowbit(only)];
				for (int k = 0; k < N; ++k) {
					for (int l = 0; l < N; ++l) {
						if (can[N*i+k][N*j+l] & (1 << num)) {
							--rest;
							draw(N * i + k, N * j + l, num, ans, can);
							break;
						}
					}
				}
			}
		}
	}
	
	if (!rest) {
		print(ans);
		return true;
	}
	
	// cut 6 min first
	int mi_n_can = 0x3f3f3f3f, nxt_row = -1, nxt_col = -1;
	for (int i = 0; i < N*N; ++i) {
		for (int j = 0; j < N*N; ++j) {
			if (ans[i][j] == '-') {
				int n_can = pop_cnt[can[i][j]];
				if (!n_can) return false;
				if (n_can < mi_n_can) {
					mi_n_can = n_can, nxt_row = i, nxt_col = j;
				}
			}
		}
	}
	
	for (int t = can[nxt_row][nxt_col]; t; t -= lowbit(t)) {
		char ans_cp[N*N][N*N];
		int can_cp[N*N][N*N];
		memcpy(ans_cp, ans, sizeof ans_cp);
		memcpy(can_cp, can, sizeof can_cp);
		draw(nxt_row, nxt_col, p2n[lowbit(t)], ans_cp, can_cp);
		if (dfs(rest - 1, ans_cp, can_cp)) return true;
	}
	return false;
}

int main() {
	for (int i = 0; i < N*N; ++i) p2n[1<<i] = i;
	for (int i = 0; i < 1 << (N*N); ++i) pop_cnt[i] = bitset<N*N>(i).count();
	
	char t;
	while (cin >> t) {
		cin.unget();
		int rest = 0;
		int can[N*N][N*N];
		char ans[N*N][N*N];
		for (int row = 0; row < N*N; ++row)
			for (int col = 0; col < N*N; ++col) can[row][col] = 0xffff;
		for (int row = 0; row < N*N; ++row) {
			for (int col = 0; col < N*N; ++col) {
				cin >> ans[row][col];
				if (ans[row][col] == '-') ++rest;
				else draw(row, col, ans[row][col] - 'A', ans, can);
			}
		}
		dfs(rest, ans, can);
		cout << "\n";
	}
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 287ms, 内存消耗: 644K, 提交时间: 2020-02-23 20:25:04

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
const int MAXC = 1024 + 10;
const int MAXR = 4096 + 10;
const int MAXP = MAXR * 4 + MAXC;
 
struct DLX {
    int n, sz;//列数，结点总数
    int sum[MAXC];//每列拥有的结点数
    int row[MAXP], col[MAXP];//结点所在的行和列
    int left[MAXP], right[MAXP], up[MAXP], down[MAXP];//十字链表
    int ansd, ans[MAXR];
 
    void init(int nn) {
        n = nn;
        for(int i = 0; i <= n; ++i) {
            up[i] = down[i] = i;
            left[i] = i - 1; right[i] = i + 1;
        }
        right[n] = 0; left[0] = n;
        sz = n + 1;
        memset(sum, 0, sizeof(sum));
    }
 
    void add_row(int r, vector<int> columns) {
        int first = sz;
        for(int i = 0, len = columns.size(); i < len; ++i) {
            int c = columns[i];
            left[sz] = sz - 1; right[sz] = sz + 1; down[sz] = c; up[sz] = up[c];
            down[up[c]] = sz; up[c] = sz;
            row[sz] = r; col[sz] = c;
            ++sum[c]; ++sz;
        }
        right[sz - 1] = first; left[first] = sz - 1;
    }
 
    void remove(int c) {
        left[right[c]] = left[c];
        right[left[c]] = right[c];
        for(int i = down[c]; i != c; i = down[i])
            for(int j = right[i]; j != i; j = right[j]) {
                up[down[j]] = up[j]; down[up[j]] = down[j]; --sum[col[j]];
            }
    }
 
    void restore(int c) {
        for(int i = up[c]; i != c; i = up[i])
            for(int j = left[i]; j != i; j = left[j]) {
                up[down[j]] = j; down[up[j]] = j; ++sum[col[j]];
            }
        left[right[c]] = c;
        right[left[c]] = c;
    }
 
    bool dfs(int d) {
        if(right[0] == 0) {
            ansd = d;
            return true;
        }
        int c = right[0];
        for(int i = right[0]; i != 0; i = right[i]) if(sum[i] < sum[c]) c = i;
        remove(c);
        for(int i = down[c]; i != c; i = down[i]) {
            ans[d] = row[i];
            for(int j = right[i]; j != i; j = right[j]) remove(col[j]);
            if(dfs(d + 1)) return true;
            for(int j = left[i]; j != i; j = left[j]) restore(col[j]);
        }
        restore(c);
        return false;
    }
 
    bool solve(vector<int> &v) {
        v.clear();
        if(!dfs(0)) return false;
        for(int i = 0; i < ansd; ++i) v.push_back(ans[i]);
        return true;
    }
};
 
DLX solver;
 
const int SLOT = 0;
const int ROW = 1;
const int COL = 2;
const int SUB = 3;
 
inline int encode(int a, int b, int c) {
    return a * 256 + b * 16 + c + 1;
}
 
void decode(int code, int &a, int &b, int &c) {
    --code;
    c = code % 16; code /= 16;
    b = code % 16; code /= 16;
    a = code;
}
 
char puzzle[16][20];
 
bool read() {
    for(int i = 0; i < 16; ++i)
        if(scanf("%s", puzzle[i]) == EOF) return false;
    return true;
}
 
int main() {
    int kase = 0;
    while(read()) {
        if(++kase != 1) printf("\n");
        solver.init(1024);
        for(int r = 0; r < 16; ++r)
            for(int c = 0; c < 16; ++c)
                for(int v = 0; v < 16; ++v)
                    if(puzzle[r][c] == '-' || puzzle[r][c] == 'A' + v) {
                        vector<int> columns;
                        columns.push_back(encode(SLOT, r, c));
                        columns.push_back(encode(ROW, r, v));
                        columns.push_back(encode(COL, c, v));
                        columns.push_back(encode(SUB, (r/4)*4+c/4, v));
                        solver.add_row(encode(r, c, v), columns);
                    }
        vector<int> ans;
        solver.solve(ans);
        for(int i = 0, len = ans.size(); i < len; ++i) {
            int r, c, v;
            decode(ans[i], r, c, v);
            puzzle[r][c] = 'A' + v;
        }
        for(int i = 0; i < 16; ++i) printf("%s\n", puzzle[i]);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 189ms, 内存消耗: 852K, 提交时间: 2019-10-08 21:29:45

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
 
using namespace std;
 
const int oo=0x3f3f3f3f;
const int nR=16*16*16+10;
const int nC=16*16*4;
const int MAX=nR*4+nC+10;
const int delta[]={1,16*16+1,16*16*2+1,16*16*3+1};
const int head=0;
 
int cnt[nC+10],st[nC+10];
int left[MAX],right[MAX],up[MAX],down[MAX];
int row[MAX],col[MAX];
struct Ans
{
	int r,c,k;
}ans[MAX];
int M,K;
 
void remove(const int& c)
{
	left[right[c]]=left[c];
	right[left[c]]=right[c];
	for(int i=down[c];i!=c;i=down[i])
		for(int j=right[i];j!=i;j=right[j])
		{
			up[down[j]]=up[j];
			down[up[j]]=down[j];
			cnt[col[j]]--;
		}
}
 
void resume(const int& c)
{
	for(int i=up[c];i!=c;i=up[i])
		for(int j=left[i];j!=i;j=left[j])
		{
			down[up[j]]=j;
			up[down[j]]=j;
			cnt[col[j]]++;
		}
	left[right[c]]=c;
	right[left[c]]=c;
}
 
bool dfs(const int& k)
{
	if(right[head]==head)
	{
		char s[300]={0};
		for(int i=0;i<k;i++)
			s[ans[st[i]].r*16+ans[st[i]].c]=ans[st[i]].k+'A';
		for(int i=0;i<16;i++)
		{
			for(int j=0;j<16;j++)
			{
				putchar(s[i*16+j]);
			}
			puts("");
		}
		return true;
	}
	
	int s=oo,c=0;
	for(int i=right[head];i!=head;i=right[i])
		if(cnt[i]<s)
		{
			s=cnt[i];
			c=i;
		}
	
	remove(c);
	for(int i=down[c];i!=c;i=down[i])
	{
		st[k]=row[i];
		for(int j=right[i];j!=i;j=right[j])
			remove(col[j]);
		if(dfs(k+1))
			return true;
		for(int j=left[i];j!=i;j=left[j])
			resume(col[j]);
	}
	
	resume(c);
	
	return false;
}
 
void init()
{
	left[head]=nC;
	right[head]=1;
	up[head]=down[head]=head;
	for(int i=1;i<=nC;i++)
	{
		left[i]=i-1;
		right[i]=(i+1)%(nC+1);
		up[i]=down[i]=i;
		cnt[i]=0;
		col[i]=i;
		row[i]=0;
	}
	M=0;
	K=nC;
}
 
int makecolhead(const int& c)
{
	K++;
	cnt[c]++;
	col[K]=c;
	row[K]=M;
	
	left[K]=right[K]=K;
	
	up[K]=c;
	down[K]=down[c];
	up[down[K]]=K;
	down[up[K]]=K;
	return K;
}
 
void addcol(const int& id,const int& c)
{
	K++;
	cnt[c]++;
	col[K]=c;
	row[K]=M;
	
	left[K]=id;
	right[K]=right[id];
	left[right[K]]=K;
	right[left[K]]=K;
	
	up[K]=c;
	down[K]=down[c];
	up[down[K]]=K;
	down[up[K]]=K;
}
 
void addrow(const int& i,const int& j,const int& k)
{
	int id;
	M++;
	ans[M].r=i;
	ans[M].c=j;
	ans[M].k=k;
	id=makecolhead(16*i+j+delta[0]);
	addcol(id,16*i+k+delta[1]);
	addcol(id,16*j+k+delta[2]);
	addcol(id,(i/4*4+j/4)*16+k+delta[3]);
}
 
int main()
{
	char str[300];
	char s[300];
	int pos;
	bool blocks=false;
	while(~scanf("%s",str))
	{
		if(blocks)
			puts("");
		else
			blocks=true;
		init();
		pos=0;
		for(int i=0;i<16;i++)
			s[pos++]=str[i];
		for(int i=1;i<16;i++)
		{
			scanf("%s",str);
			for(int j=0;j<16;j++)
				s[pos++]=str[j];
		}
		for(int i=0;i<16;i++)
			for(int j=0;j<16;j++)
				if(s[i*16+j]=='-')
					for(int k=0;k<16;k++)
						addrow(i,j,k);
				else
					addrow(i,j,s[i*16+j]-'A');
		
		dfs(0);
	}
	return 0;
}