解题思路
此题是解异性数独,代码写起来比较繁琐。
首先按照题意求连通块,转化为普通数独。然后用正常求解数独的 DLX 精确覆盖算法即可解决。
另外应注意一旦计算出多解时要及时返回,防止超时。
参考代码
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int N = 9*9*9;
const int M = 9*9*4;
struct DLX {
int l, r, u, d;
int row, col;
} dlx[(N+1)*(M+1)+M+1];
struct row_info {
int head;
int row, col, value; // original info
} rinfo[N+1];
struct info {
int value;
bool banned_dirt[4];
int idx;
} a[9][9];
int sz[M+1], idx, bidx, ans[9][9], final_ans[9][9], ans_cnt;
int dirt[4][2] = {
{-1, 0}, {0, 1}, {1, 0}, {0, -1}
};
bool hasr[9][10], hasc[9][10], hasb[9][10];
void Init(int m) {
for(int i=0; i<=m; ++i) {
dlx[i].u = dlx[i].d = i;
dlx[i+1].l = i;
dlx[i].r = i+1;
sz[i] = 0;
}
dlx[m].r = 0;
dlx[0].l = m;
idx = m+1;
}
void Insert(int r, int c) {
sz[c]++;
// U/D
dlx[dlx[c].u].d = idx;
dlx[idx].u = dlx[c].u;
dlx[idx].d = c;
dlx[c].u = idx;
dlx[idx].row = r;
dlx[idx].col = c;
// L/R
if(rinfo[r].head == -1)
rinfo[r].head = dlx[idx].l = dlx[idx].r = idx;
else {
dlx[dlx[rinfo[r].head].l].r = idx;
dlx[idx].l = dlx[rinfo[r].head].l;
dlx[idx].r = rinfo[r].head;
dlx[rinfo[r].head].l = idx;
}
idx++;
}
void Remove(int c) {
// Column
dlx[dlx[c].l].r = dlx[c].r;
dlx[dlx[c].r].l = dlx[c].l;
// Row
for(int i=dlx[c].d; i!=c; i=dlx[i].d) {
for(int j=dlx[i].r; j!=i; j=dlx[j].r) {
dlx[dlx[j].u].d = dlx[j].d;
dlx[dlx[j].d].u = dlx[j].u;
sz[dlx[j].col]--;
}
}
}
void Resume(int c) {
// Column
dlx[dlx[c].l].r = c;
dlx[dlx[c].r].l = c;
// Row
for(int i=dlx[c].u; i!=c; i=dlx[i].u) {
for(int j=dlx[i].l; j!=i; j=dlx[j].l) {
dlx[dlx[j].u].d = j;
dlx[dlx[j].d].u = j;
sz[dlx[j].col]++;
}
}
}
void Dance() {
if(ans_cnt > 1) return;
if(dlx[0].r == 0) {
ans_cnt++;
if(ans_cnt == 1) {
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
final_ans[i][j] = ans[i][j];
}
}
}
return;
}
else {
int minsz = 0x3f3f3f3f, c;
for(int i=dlx[0].r; i!=0; i=dlx[i].r) {
if(sz[i] == 0) return;
if(sz[i] < minsz) {
minsz = sz[i];
c = i;
if(minsz == 1) break;
}
}
Remove(c);
for(int i=dlx[c].d; i!=c; i=dlx[i].d) {
ans[rinfo[dlx[i].row].row][rinfo[dlx[i].row].col] = rinfo[dlx[i].row].value;
for(int j=dlx[i].r; j!=i; j=dlx[j].r) {
Remove(dlx[j].col);
}
Dance();
for(int j=dlx[i].l; j!=i; j=dlx[j].l) {
Resume(dlx[j].col);
}
}
Resume(c);
}
}
bool Judge(int x, int y) {
if(x>=0 && x<9 && y>=0 && y<9)
return true;
else return false;
}
void DFS(int x, int y) {
a[x][y].idx = bidx;
for(int i=0; i<4; ++i) {
if(a[x][y].banned_dirt[i]) continue;
int nx = x + dirt[i][0];
int ny = y + dirt[i][1];
if(Judge(nx, ny) && a[nx][ny].idx==-1) {
a[nx][ny].idx = bidx;
DFS(nx, ny);
}
}
}
int main(int argc, char const *argv[]) {
int t, bin;
scanf("%d", &t);
for(int cases=1; cases<=t; ++cases) {
printf("Case %d:\n", cases);
memset(a, 0, sizeof a);
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
a[i][j].idx = -1;
scanf("%d", &bin);
stack<int> s;
for(int k=0; k<4; ++k) {
s.push(bin&1);
bin >>= 1;
}
while(!s.empty()) {
a[i][j].value = a[i][j].value*2 + s.top();
s.pop();
}
for(int k=0; k<4; ++k) {
a[i][j].banned_dirt[k] = bin & 1;
bin >>= 1;
}
}
}
bidx = 0;
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
if(a[i][j].idx == -1) {
DFS(i, j);
bidx++;
}
}
}
memset(hasr, false, sizeof hasr);
memset(hasc, false, sizeof hasc);
memset(hasb, false, sizeof hasb);
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
if(a[i][j].value) {
hasr[i][a[i][j].value] = true;
hasc[j][a[i][j].value] = true;
hasb[a[i][j].idx][a[i][j].value] = true;
}
}
}
Init(M);
int n = 0;
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
int sidx = i*9 + j;
if(a[i][j].value) {
rinfo[n].row = i;
rinfo[n].col = j;
rinfo[n].value = a[i][j].value;
rinfo[n].head = -1;
Insert(n, 1 + sidx);
Insert(n, 81 + i*9+a[i][j].value);
Insert(n, 162 + j*9+a[i][j].value);
Insert(n, 243 + a[i][j].idx*9+a[i][j].value);
n++;
}
else {
for(int k=1; k<=9; ++k) {
if(!hasr[i][k] && !hasc[j][k] && !hasb[bidx][k]) {
rinfo[n].row = i;
rinfo[n].col = j;
rinfo[n].value = k;
rinfo[n].head = -1;
Insert(n, 1 + sidx);
Insert(n, 81 + i*9+k);
Insert(n, 162 + j*9+k);
Insert(n, 243 + a[i][j].idx*9+k);
n++;
}
}
}
}
}
ans_cnt = 0;
Dance();
if(ans_cnt == 0) printf("No solution\n");
if(ans_cnt == 1) {
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
printf("%d", final_ans[i][j]);
}
printf("\n");
}
}
if(ans_cnt == 2) printf("Multiple Solutions\n");
}
return 0;
}
还不快抢沙发