加载中…HDU 3909 Sudoku 2011 Multi-University Training Contest 7 - Host by ECNU
(2011-08-02 18:24:07)
标签：
hdu3909dlxit |
分类： 搜索 |
题目描述：
DLX，求数独，不一样的地方就是判断是否多解，在dfs得到答案的时候判断一下就可以。模板题目。
代码如下：
U[size]
= up, D[size] = down;
L[size]
= left, R[size] = right;
D[up] =
U[down] = R[left] = L[right] = size;
return
size++;
size =
0;
head =
node(0, 0, 0, 0);
for
(int j = 1; j <= M; ++j) {
CH[j] = node(size, size,
L[head], head), S[j] = 0;
}
for
(int i = 1; i <= N; ++i) {
int row = -1, k;
for (int j = 1; j
<= M; ++j) {
if (!mat[i][j]) continue;
if (row == -1) {
row =
node(U[CH[j]], CH[j], size, size);
RH[row] =
i, CH[row] = CH[j], ++S[j];
} else {
k =
node(U[CH[j]], CH[j], L[row], row);
RH[k] = i,
CH[k] = CH[j], ++S[j];
}
}
}
L[R[c]]
= L[c], R[L[c]] = R[c];
for
(int i = D[c]; i != c; i = D[i]) {
for (int j = R[i]; j != i; j =
R[j]) {
U[D[j]] = U[j], D[U[j]] = D[j];
--S[CH[j]];
}
}
for
(int i = U[c]; i != c; i = U[i]) {
for (int j = L[i]; j != i; j =
L[j]) {
++S[CH[j]];
U[D[j]] = D[U[j]] = j;
}
}
L[R[c]]
= R[L[c]] = c;
if
(R[head] == head) {
anscnt++;
if (anscnt == tar)
{
len = k - 1;
return true;
}
else return false;
//len = k - 1;
//return true;
}
int s =
inf, c;
for
(int t = R[head]; t != head; t = R[t]) {
if (S[t] < s) s
= S[t], c = t;
}
remove(c);
for
(int i = D[c]; i != c; i = D[i]) {
O[k] = RH[i];
for (int j = R[i]; j != i; j =
R[j]) {
remove(CH[j]);
}
if (dfs(k + 1)) {
return true;
}
for (int j = L[i]; j != i; j =
L[j]) {
resume(CH[j]);
}
}
resume(c);
return
false;
memset(mat, false, sizeof(mat));
//const
int N = 16, NN = N * N, n = 4;
for
(int i = 1; i <= N; ++i)
for (int j = 1; j
<= N; ++j)
for (int k = 1; k <= N; ++k)
if
(sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1)
mat[(i - 1) * NN + (j - 1) * N
+ k][(i - 1) * N + j] = true;
for
(int i = 1; i <= N; ++i)
for (int k = 1; k
<= N; ++k)
for (int j = 1; j <= N; ++j)
if
(sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1)
mat[(i - 1) * NN + (j - 1) * N
+ k][NN + (i - 1) * N + k] = true;
for
(int j = 1; j <= N; ++j)
for (int k = 1; k
<= N; ++k)
for (int i = 1; i <= N; ++i)
if
(sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1)
mat[(i - 1) * NN + (j - 1) * N
+ k][NN * 2 + (j - 1) * N + k] = true;
int
region;
for
(int i = 1; i <= N; ++i)
for (int j = 1; j
<= N; ++j)
for (int k = 1; k <= N; ++k)
{
region =
((i - 1) / n) * n + (j - 1) / n + 1;
if
(sudoku[i][j] == '-' || sudoku[i][j] == 'A' + k - 1)
mat[(i - 1) * NN + (j - 1) * N
+ k][NN * 3 + (region - 1) * N + k] = true;
}
if (x
== '.' || x == '-') return '-';
if (x
>= '0' && x
<= '9') return 'A' + x - '1';
return
'J' + x - 'A';
for(int
i = 1; i <= N; i++)
{
for(int j = 1; j
<= N; j++)
{
if (myans[i][j] <= 'I')
myans[i][j]
= '1' + myans[i][j] - 'A';
else
{
myans[i][j]
= 'A' + myans[i][j] - 'J';
}
putchar(myans[i][j]);
}
putchar('\n');
}
while(scanf("%d", &n) !=
EOF)
{
N = n * n; NN = N * N;
for(int i = 1; i
<= N; i++)
{
scanf("%s", sudoku[i] + 1);
for(int j = 1; j <= N; j++)
sudoku[i][j] = jeo(sudoku[i][j]);
}
anscnt = 0; tar = 1;
make();
init(N * N * N, 4 * N *
N);
dfs(1);
if (anscnt == 0) printf("No
Solution\n");
else
{
for (int i = 1; i <= len; ++i)
{
int x =
(O[i] - 1) / NN + 1;
O[i] -= (x
- 1) * NN;
int y =
(O[i] - 1) / N + 1;
O[i] -= (y
- 1) * N;
int z =
O[i];
myans[x][y]
= 'A' + z - 1;
}
anscnt = 0; tar = 2;
make();
init(N * N * N, 4 * N * N);
dfs(1);
if (anscnt == 2) printf("Multiple
Solutions\n");
else
{
bool flag =
true;
for(int i =
1; i <= N && flag;
i++)
for(int j = 1; j
<= N && flag;
j++)
if (sudoku[i][j] != '-')
{
char tmp =
sudoku[i][j];
sudoku[i][j] = '-';
anscnt = 0;
tar = 2;
make();
init(N * N
* N, 4 * N * N);
dfs(1);
if (anscnt
== 1)
{
flag = false;
break;
}
sudoku[i][j] = tmp;
}
if (!flag)
printf("Not Minimal\n");
else
output();
}
}
}
return
0;
DLX，求数独，不一样的地方就是判断是否多解，在dfs得到答案的时候判断一下就可以。模板题目。
代码如下：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v
<< ": "
<< (v)
<< endl
using namespace std;
typedef long long LL;
const int maxN = 20 * 20 * 20, maxM = 4 * 20 * 20;
int N, NN, n;
const int max_size = maxN * maxM;
const int inf = 0x3f3f3f3f;
int L[max_size], R[max_size], U[max_size], D[max_size],
CH[max_size], RH[max_size];
int S[maxM], O[maxM];
int head, size;
int node(int up, int down, int left, int right) {
}
bool mat[maxN][maxM];
void init(int N, int M) {
}
void remove(const int &c) {
}
void resume(const int &c) {
}
int len;
int anscnt, tar;
bool dfs(const int &k) {
}
char sudoku[20][20], myans[20][20];
void make()
{
}
char jeo(char x)
{
}
void output()
{
}
int main()
{
}
喜欢
0
赠金笔