poj3074 Sudoku--舞蹈链数独

原题链接：​​http://poj.org/problem?id=3074​​

题意：给定一个9*9的数独，求解。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
const int MAXC = 81 * 4 + 10;
const int MAXR = 81 * 9 + 10;
const int MAXN = MAXC*MAXR + 10;

using namespace std;

int cnt;
char s[200];
int U[MAXN], D[MAXN], L[MAXN], R[MAXN];
int C[MAXN], M[MAXN];//节点所在列与行
int H[MAXR];//行头指针
int S[MAXC];//储存每列的元素数量
int ans[100];

void init(int n)
{
  for (int i = 0; i <= n; i++)
  {
    U[i] = D[i] = i;
    L[i] = i - 1;
    R[i] = i + 1;
    S[i] = 0;
  }
  R[n] = 0;
  L[0] = n;
  S[0] = INF + 1;
  cnt = n + 1;
  memset(H, 0, sizeof(H));
}

void link(int r, int c)
{
  M[cnt] = r;//记录行列
  C[cnt] = c;
  U[cnt] = U[c];//上下连接
  D[cnt] = c;
  D[U[c]] = cnt;
  U[c] = cnt;

  if (H[r] == 0)//左右连接
    H[r] = L[cnt] = R[cnt] = cnt;
  else
  {
    L[cnt] = L[H[r]];
    R[L[H[r]]] = cnt;
    L[H[r]] = cnt;
    R[cnt] = H[r];
  }

  S[c]++;
  cnt++;
}


void remove(int c)
{
  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[C[j]]--;
    }
  }
}

void resume(int c)
{
  L[R[c]] = c;
  R[L[c]] = c;
  for (int i = U[c]; i != c; i = U[i])
  {
    for (int j = L[i]; j != i; j = L[j])
    {
      U[D[j]] = j;
      D[U[j]] = j;
      S[C[j]]++;
    }
  }
}

bool dance(int k)
{
  if (R[0] == 0)
  {
    sort(ans, ans + 81);
    int p = 0;
    for (int i = 0; i < 9; i++)
    {
      for (int j = 0; j < 9; j++)
      {
        int num = ans[p++];
        num = num - (i * 9 + j) * 9;
        printf("%d", num);
      }
    }
    printf("\n");
    return true;
  }

  int c;
  int t = INF;
  for (int i = R[0]; i != 0; i = R[i])
  {
    if (S[i] < t)
    {
      t = S[i];
      c = i;
    }
  }

  remove(c);
  for (int i = D[c]; i != c; i = D[i])
  {
    ans[k] = M[i];
    for (int j = R[i]; j != i; j = R[j])
      remove(C[j]);
    if (dance(k + 1))
      return true;
    for (int j = L[i]; j != i; j = L[j])
      resume(C[j]);
  }
  resume(c);
  return false;
}

void build()
{
  int p = 0;
  init(9 * 9 * 4);
  for (int i = 0; i < 9; i++)
  {
    for (int j = 1; j <= 9; j++, p++)
    {
      int base = (i * 9 + j - 1) * 9;
      if (s[p] == '.')
      {
        for (int k = 1; k <= 9; k++)
        {
          int r = base + k;
          link(r, i * 9 + k);//第i行有数字k
          link(r, 81 + (j - 1) * 9 + k);//第j列有数字k
          link(r, 81 * 2 + ((j - 1) / 3 * 3 + i / 3) * 9 + k);//第k块有数字k
          link(r, 81 * 3 + i * 9 + j);//第i行j列有一个数字（限制一个格子只填一个数）
        }
      }
      else
      {
        int k = s[p] - '0';
        int r = base + k;
        link(r, i * 9 + k);//第i行有数字k
        link(r, 81 + (j - 1) * 9 + k);//第j列有数字k
        link(r, 81 * 2 + ((j - 1) / 3 * 3 + i / 3) * 9 + k);//第k块有数字k
        link(r, 81 * 3 + i * 9 + j);//第i行j列有一个数字（限制一个格子只填一个数）
      }
    }
  }
}

int main()
{
  while (~scanf("%s", s))
  {
    if (strcmp(s, "end") == 0)
      break;
    build();
    dance(0);
  }
  return 0;
}