#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;
}
void add_node(int r0, int c0)
{
    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;
}

• 测试数据 (15136) xuhaoran510 2011-01-31 20:41:17
  • 3x (36) mato_no1 2011-01-31 21:05:31
  • 用G++就AC了 (45) mato_no1 2011-01-31 21:22:17
    • Re:用G++就AC了 (63) haihongblog 2018-11-19 15:55:17
  • Re:测试数据 (33) syb3181 2016-06-15 15:05:16