精确覆盖 Dance Links
精确覆盖 Dance Links
1 | template <int MXNODE = 5000> // 稀疏矩阵最大点数 |
- 37. 解数独
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
template <int MXNODE = 5000> // 稀疏矩阵最大点数
struct DLX {
int n, m, cur; // 行 列 新节点指针
int h[MXNODE]; //每行的头指针
int u[MXNODE], d[MXNODE], l[MXNODE], r[MXNODE]; //每个点的上下左右指针
int row[MXNODE], col[MXNODE]; //每个点所在行,列
int s[MXNODE]; //每列的节点数
int ans[MXNODE]; //选了那些行
DLX(int n, int m): n(n), m(m) {
cur = 0;
memset(h, 0, sizeof(u));
memset(u, 0, sizeof(u));
memset(d, 0, sizeof(d));
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(s, 0, sizeof(s));
memset(ans, 0, sizeof(ans));
init();
}
void init(){ //初始化第0行的列表头
for(int y=0; y<=m; y++){
u[y] = d[y] = y;
l[y] = y-1; r[y] = y+1;
}
l[0]=m; r[m]=0; cur=m+1; //下一个点的编号
}
//尾插法
void link(int x,int y){ //在x行y列插入点
// cout << x << " " << y << " " << cur << endl;
row[cur]=x; col[cur]=y; s[y]++;
// 列表头y，原先y <--> u[y]，变为y <--> cur <--> u[y]
u[cur]=u[y]; // cur --> u[y]
d[u[y]]=cur; // cur <--> u[y]
d[cur]=y; // y <-- cur <--> u[y]
u[y]=cur; // y <--> cur <--> u[y]
// 行表头h[x]
if (h[x] == 0) {
h[x] = r[cur] = l[cur] = cur;
} else {
// 原先 l[h[x]] <--> h[x]，变为l[h[x]] <--> cur <--> h[x]
l[cur]=l[h[x]]; // l[h[x]] <-- cur
r[l[h[x]]]=cur; // l[h[x]] <--> cur
r[cur]=h[x]; // l[h[x]] <--> cur --> h[x]
l[h[x]]=cur; // l[h[x]] <--> cur <--> h[x]
}
cur++;
}
void remove(int y){ //删除y列与关联行
/*
a <--> b <--> c
to
a <-- b --> c
<------->
*/
r[l[y]]=r[y], l[r[y]]=l[y]; // 虚拟表头删除当前点
for(int i=d[y]; i!=y; i=d[i]) //向下
for(int j=r[i]; j!=i; j=r[j]) //向右
u[d[j]]=u[j], d[u[j]]=d[j], s[col[j]]--;
}
void resume(int y){ //恢复y列与关联行
r[l[y]]=y, l[r[y]]=y;
for(int i=u[y]; i!=y; i=u[i]) //向上
for(int j=l[i]; j!=i; j=l[j]) //向左
u[d[j]]=j, d[u[j]]=j, s[col[j]]++;
}
bool dance(int dep, vector<vector<char>>& board){
if(r[0]==0){
for (int i=0; i<dep; i++) {
// cout << ans[i] << " ";
// 解码所选的行在数独中的信息
// ans[i] = (r*9+c)*9+k+1
int k = (ans[i]-1)%9;
int c = (ans[i]-1)/9%9;
int r = (ans[i]-1)/9/9;
board[r][c] = char(k+'0'+1);
}
// cout << "\n";
return true;
}
int y=r[0]; //找到点最少的列
for(int i=r[0];i;i=r[i]) if(s[i]<s[y]) y=i;
remove(y);
for(int i=d[y];i!=y;i=d[i]) {
//在y列含1的行中选择一行作为答案，这一行存在1的列也需要关联删除才能保证精准覆盖
ans[dep]=row[i];
for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
if(dance(dep+1, board)) return true;
for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
}
resume(y);
return false;
}
};
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
/*
约束列
81格只能填一个数字 81列
每行每数只能填一次 81列
每列每数只能填一次 81列
每宫每数只能填一次 81列
共324列
决策行
每个格子有9种选法,共81格，共计729行
每行需要4列为1，共计2916个点
构建矩阵还需要第0行虚拟表头325个列节点
*/
DLX dlx(729, 324);
for (int r=0; r<9; r++) { // 数独行
for (int c=0; c<9; c++) { // 数独列
bool all = board[r][c] == '.';
for (int k=(all?0:board[r][c]-'0'-1); k<(all?9:board[r][c]-'0'); k++) { // 数独选择数字
// cout << r << " " << c << " " << k << "\n";
int row = (r*9+c)*9+k+1; // 行
int clo1 = r*9+c+1; // i行j列填了数字
int clo2 = 81+(r*9+k+1); // i行填了k
int clo3 = 81*2+(c*9+k+1); // j列填了k
int clo4 = 81*3+((r/3*3+c/3)*9+k+1); // r/3*3+c/3宫填了k
dlx.link(row, clo1);
dlx.link(row, clo2);
dlx.link(row, clo3);
dlx.link(row, clo4);
}
}
}
dlx.dance(0, board);
}
}; - 52. N 皇后 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
template <int MXNODE = 5000> // 稀疏矩阵最大点数
struct DLX {
int n, m, cur; // 行 列 新节点指针
int h[MXNODE]; //每行的头指针
int u[MXNODE], d[MXNODE], l[MXNODE], r[MXNODE]; //每个点的上下左右指针
int row[MXNODE], col[MXNODE]; //每个点所在行,列
int s[MXNODE]; //每列的节点数
int ans = 0;
DLX(int n, int m): n(n), m(m) {
cur = ans = 0;
memset(h, 0, sizeof(u));
memset(u, 0, sizeof(u));
memset(d, 0, sizeof(d));
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(s, 0, sizeof(s));
init();
}
void init(){ //初始化第0行的列表头
for(int y=0; y<=m; y++){
u[y] = d[y] = y;
l[y] = y-1; r[y] = y+1;
}
l[0]=m; r[m]=0; cur=m+1; //下一个点的编号
}
//尾插法 要逐行逐列顺序插入
void link(int x,int y){ //在x行y列插入点
row[cur]=x; col[cur]=y; s[y]++;
// 列表头y，原先y <--> u[y]，变为y <--> cur <--> u[y]
u[cur]=u[y]; // cur --> u[y]
d[u[y]]=cur; // cur <--> u[y]
d[cur]=y; // y <-- cur <--> u[y]
u[y]=cur; // y <--> cur <--> u[y]
// 行表头h[x]
if (h[x] == 0) {
h[x] = r[cur] = l[cur] = cur;
} else {
// 原先 l[h[x]] <--> h[x]，变为l[h[x]] <--> cur <--> h[x]
l[cur]=l[h[x]]; // l[h[x]] <-- cur
r[l[h[x]]]=cur; // l[h[x]] <--> cur
r[cur]=h[x]; // l[h[x]] <--> cur --> h[x]
l[h[x]]=cur; // l[h[x]] <--> cur <--> h[x]
}
cur++;
}
void remove(int y){ //删除y列与关联行
/*
a <--> b <--> c
to
a <-- b --> c
<------->
*/
r[l[y]]=r[y], l[r[y]]=l[y]; // 虚拟表头删除当前点
for(int i=d[y]; i!=y; i=d[i]) //向下
for(int j=r[i]; j!=i; j=r[j]) //向右
u[d[j]]=u[j], d[u[j]]=d[j], s[col[j]]--;
}
void resume(int y){ //恢复y列与关联行
r[l[y]]=y, l[r[y]]=y;
for(int i=u[y]; i!=y; i=u[i]) //向上
for(int j=l[i]; j!=i; j=l[j]) //向左
u[d[j]]=j, d[u[j]]=j, s[col[j]]++;
}
void dance(int dep, int ed){
if (dep == ed) {
ans++;
return ;
}
int y=r[0]; //找到点最少的列
for(int i=r[0];i && i<=ed;i=r[i]) if(s[i]<s[y]) y=i;
remove(y);
for(int i=d[y];i!=y;i=d[i]) {
//在y列含1的行中选择一行作为答案，这一行存在1的列也需要关联删除才能保证精准覆盖
for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
dance(dep+1, ed);
for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
}
resume(y);
}
};
class Solution {
public:
int totalNQueens(int n) {
int r = n*n, c = n+n+(2*n-1)+(2*n-1);
DLX<500> dlx(r, c);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
int row = i*n+j+1;
int clo1 = i+1;
int clo2 = n + j+1;
int clo3 = 2*n + i-j+(n-1)+1;
int clo4 = 2*n + (2*n-1) + i+j+1;
// cout <<row << " " << clo1 <<" " <<clo2 <<" " << clo3 <<" " <<clo4 <<endl;
dlx.link(row, clo1);
dlx.link(row, clo2);
dlx.link(row, clo3);
dlx.link(row, clo4);
}
}
dlx.dance(0, n);
return dlx.ans;
}
};