Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 神犇们看一下……DLX都超……无语了

Posted by mato_no1 at 2011-01-31 20:21:19 on Problem 3074
```#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define ra(i) for (int i=1; i<=9; i++)
const int PX[10][10] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
0, 7, 7, 7, 8, 8, 8, 9, 9, 9,
0, 7, 7, 7, 8, 8, 8, 9, 9, 9,
0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
PY[10][10] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 2, 3, 1, 2, 3, 1, 2, 3,
0, 4, 5, 6, 4, 5, 6, 4, 5, 6,
0, 7, 8, 9, 7, 8, 9, 7, 8, 9,
0, 1, 2, 3, 1, 2, 3, 1, 2, 3,
0, 4, 5, 6, 4, 5, 6, 4, 5, 6,
0, 7, 8, 9, 7, 8, 9, 7, 8, 9,
0, 1, 2, 3, 1, 2, 3, 1, 2, 3,
0, 4, 5, 6, 4, 5, 6, 4, 5, 6,
0, 7, 8, 9, 7, 8, 9, 7, 8, 9};
const int MAXN = 730, MAXM = 325, INF = ~0U >> 2;
struct DLnode {
int r, c, U, D, L, R;
} d[MAXN * MAXM];
bool A[MAXN][MAXM];
int a[10][10], ROW[10][10][10], COL[4][10][10], row_id[MAXN], col_id[MAXM], rrr[3][MAXN];
int n, m, nodes, cols[MAXM], rowh[MAXN], reslen, res[MAXN];
bool finished;
void init_d()
{
re3(i, 0, m) {
d[i].r = 0; d[i].c = d[i].U = d[i].D = i; d[i].L = i - 1; d[i].R = i + 1;
}
d[0].L = m; d[m].R = 0; nodes = m + 1; finished = 0;
}
{
d[nodes].r = r0; d[nodes].c = c0; cols[c0]++;
d[nodes].U = d[c0].U; d[nodes].D = c0; d[c0].U = nodes; d[d[nodes].U].D = nodes;
if (rowh[r0]) {
d[nodes].L = d[rowh[r0]].L; d[nodes].R = rowh[r0]; d[rowh[r0]].L = nodes; d[d[nodes].L].R = nodes;
} else {
d[nodes].L = d[nodes].R = rowh[r0] = nodes;
}
nodes++;
}
void prepare()
{
memset(row_id, -1, sizeof(row_id));
memset(col_id, -1, sizeof(col_id));
ra(i) ra(j) {
int x = a[i][j], P = PX[i][j];
if (x) {
ra(k) {
row_id[ROW[i][k][x]] = 0;
row_id[ROW[k][j][x]] = 0;
row_id[ROW[PX[P][k]][PY[P][k]][x]] = 0;
row_id[ROW[i][j][k]] = 0;
}
col_id[COL[0][i][x]] = 0;
col_id[COL[1][j][x]] = 0;
col_id[COL[2][P][x]] = 0;
col_id[COL[3][i][j]] = 0;
}
}
n = 0; m = 0;
re3(i, 1, MAXN) if (row_id[i]) row_id[i] = ++n;
re3(i, 1, MAXM) if (col_id[i]) col_id[i] = ++m;
memset(rowh, 0, n << 2);
init_d();
re3(i, 1, MAXN) if (row_id[i]) re3(j, 1, MAXM) if (col_id[j] && A[i][j]) add_node(row_id[i], col_id[j]);
ra(i) ra(j) ra(k) {
int x = row_id[ROW[i][j][k]];
if (x) {rrr[0][x] = i; rrr[1][x] = j; rrr[2][x] = k;}
}
}
void delLR(int x)
{
d[d[x].L].R = d[x].R; d[d[x].R].L = d[x].L;
}
void delUD(int x)
{
d[d[x].U].D = d[x].D; d[d[x].D].U = d[x].U;
}
void resuLR(int x)
{
d[d[x].L].R = x; d[d[x].R].L = x;
}
void resuUD(int x)
{
d[d[x].U].D = x; d[d[x].D].U = x;
}
void delcol(int c0)
{
delLR(c0);
for (int i=d[c0].D; i != c0; i = d[i].D) {
for (int j=d[i].R; j != i; j = d[j].R) {delUD(j); cols[d[j].c]--;}
}
}
void resucol(int c0)
{
for (int i=d[c0].U; i != c0; i = d[i].U) {
for (int j=d[i].L; j != i; j = d[j].L) {cols[d[j].c]++; resuUD(j);}
}
resuLR(c0);
}
void dfs(int v)
{
if (!d[0].R) {reslen = v; finished = 1; return;}
int min = INF, c0;
for (int i=d[0].R; i; i = d[i].R) if (cols[i] < min) {min = cols[i]; c0 = i;}
delcol(c0);
for (int i=d[c0].D; i != c0; i = d[i].D) {
for (int j=d[i].R; j != i; j = d[j].R) delcol(d[j].c);
res[v] = d[i].r;
dfs(v + 1);
if (finished) return;
res[v] = 0;
for (int j=d[i].L; j != i; j = d[j].L) resucol(d[j].c);
}
resucol(c0);
}
void solve()
{
int No = 0;
ra(i) ra(j) ra(k) ROW[i][j][k] = ++No;
No = 0;
re(i, 4) ra(j) ra(k) COL[i][j][k] = ++No;
memset(A, 0, sizeof(A));
ra(i) ra(j) {
int P = PX[i][j];
ra(k) {
A[ROW[i][j][k]][COL[0][i][k]] = 1;
A[ROW[i][j][k]][COL[1][j][k]] = 1;
A[ROW[i][j][k]][COL[2][P][k]] = 1;
A[ROW[i][j][k]][COL[3][i][j]] = 1;
}
}
char s[100];
while (1) {
gets(s);
if (!strcmp(s, "end")) break;
int No = 0;
ra(i) ra(j) {if (s[No] == '.') a[i][j] = 0; else a[i][j] = s[No] - 48; No++;}
prepare();
dfs(0);
re(i, reslen) {
int j = res[i];
a[rrr[0][j]][rrr[1][j]] = rrr[2][j];
}
ra(i) ra(j) printf("%d", a[i][j]); puts("");
}
}
int main()
{
solve();
return 0;
}

```

Followed by: