예제 6.9 수 독 LA 2659

1. 제목 설명: 클릭 하여 링크 열기
2. 문제 풀이 방향: 본 문 제 는 DLX 알고리즘 을 이용 하여 해결한다.교묘 한 점 은 사실 전환 과정 에 있다.DLX 알고리즘 은 정확 한 덮어 쓰기 문 제 를 해결 합 니 다. 그러면 어떻게 하나의 디지털 문 제 를 정확 한 덮어 쓰기 문제 로 바 꿉 니까?우 리 는 정확 한 커버 문 제 는 사실 일부 줄 을 선택 하 는 것 이 고 최종 적 으로 모든 열 을 적당 하 게 커버 할 수 있 도록 요구 하 는 것 을 발견 할 수 있다.즉, 사용 가능 한 결정 을 대표 하고 '1' 은 이 줄 이 완성 할 수 있 는 임 무 를 나타 낸다.우 리 는 이 틀 을 적용 하려 고 시도 했다.
먼저, 모든 결정 은 하나의 3 원 그룹 (r, c, v) 으로 표시 할 수 있 습 니 다. 즉, (r, c) 이 칸 에 알파벳 v 를 작성 할 수 있 습 니 다.곱셈 원리 에 따 르 면 모두 16 * 16 * 16 = 4096 가지 결정, 즉 4096 줄 이 있다.
다음, 우 리 는 모두 네 가지 임무 가 있다.
Slot (a, b) 는 a 줄 을 표시 하고 b 열의 칸 은 알파벳 이 있어 야 합 니 다.
Row (a, b) 는 a 줄 에 알파벳 b 가 있어 야 한 다 는 것 을 나타 낸다.
Col (a, b) 은 a 열 에 알파벳 b 가 있어 야 한 다 는 것 을 나타 낸다.
Sub (a, b) 는 a 번 째 자 방진 에 알파벳 b 가 있어 야 한 다 는 것 을 나타 낸다.
곱셈 원리 에 따 르 면 모두 16 * 16 * 4 = 1024 열 이 있다 는 것 을 알 수 있다.
마지막 으로 '1' 은 하나의 결정 이 하나의 임 무 를 완성 한 것 을 대표 한다. 상기 결정 은 3 원 조 (i, j, k) 의 형식 으로 쓸 수 있 고 4 가지 임 무 를 달성 한 것 을 발견 할 수 있다. Grid (i, j), Row (i, k), Col (i, k) 과 Sub (Pij, k) (Pij 는 i 행, j 열 이 있 는 서브 방진 의 번호) 는 모두 4096 * 4 = 16384 개의 결점 이 있다 고 계산 하기 어렵 지 않다.
이렇게 해서 상기 문 제 는 정확 한 덮어 쓰기 문제 로 성공 적 으로 전환 되 었 고 DLX 알고리즘 으로 풀 수 있 습 니 다.여기 서 3 원 그룹 을 인 코딩 하여 줄 번 호 를 얻 고 마지막 으로 디 코딩 을 해서 최종 적 으로 풀 수 있 습 니 다.
3. 코드:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cassert>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<functional>
using namespace std;

#define me(s) memset(s,0,sizeof(s))
#define pb push_back
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair <int, int> P;

const int maxr=5000;
const int maxn=2000;
const int maxnode=20000;

struct DLX    //DLX  
{
    int n,sz;
    int S[maxn];

    int row[maxnode],col[maxnode];
    int L[maxnode],R[maxnode],U[maxnode],D[maxnode];

    int ansd,ans[maxr];

    void init(int n)
    {
        this->n=n;

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

    void addRow(int r,vector<int>columns)
    {
        int first=sz;
        for(int i=0;i<columns.size();i++)
        {
            int c=columns[i];
            L[sz]=sz-1,R[sz]=sz+1,D[sz]=c,U[sz]=U[c];
            D[U[c]]=sz,U[c]=sz;
            row[sz]=r;col[sz]=c;
            S[c]++,sz++;
        }
        R[sz-1]=first;L[first]=sz-1;
    }

    #define FOR(i,A,s) for(int i=A[s];i!=s;i=A[i])

    void remove(int c)
    {
        L[R[c]]=L[c];
        R[L[c]]=R[c];
        FOR(i,D,c)
        FOR(j,R,i)
        {
            U[D[j]]=U[j],D[U[j]]=D[j],--S[col[j]];
        }
    }

    void restore(int c)
    {
        FOR(i,U,c)
        FOR(j,L,i)
        {
            ++S[col[j]],U[D[j]]=j;D[U[j]]=j;
        }
        L[R[c]]=c;R[L[c]]=c;
    }

    bool dfs(int d)
    {
        if(R[0]==0)
        {
            ansd=d;return true;
        }

        int c=R[0];
        FOR(i,R,0)if(S[i]<S[c])c=i;

        remove(c);
        FOR(i,D,c)
        {
            ans[d]=row[i];
            FOR(j,R,i)remove(col[j]);
            if(dfs(d+1))return true;
            FOR(j,L,i)restore(col[j]);
        }
        restore(c);
        return false;
    }

    bool solve(vector<int>&v)
    {
        v.clear();
        if(!dfs(0))return false;
        for(int i=0;i<ansd;i++)
            v.push_back(ans[i]);
        return true;
    }
};

DLX solver;

const int SLOT=0;
const int ROW=1;
const int COL=2;
const int SUB=3;

int encode(int a,int b,int c)// ，          ， 1    ，     1024
{
    return a*256+b*16+c+1;
}

void decode(int code,int&a,int&b,int&c)
{
    code--;
    c=code%16;code/=16;
    b=code%16;code/=16;
    a=code;
}
char puzzle[16][20];

bool read()
{
    for(int i=0;i<16;i++)
        if(scanf("%s",puzzle[i])!=1)return false;
    return true;
}

int main()
{
    int rnd=0;
    while(read())
    {
        if(rnd++)printf("
");
        solver.init(1024);  //   1024 
        for(int r=0;r<16;r++)
            for(int c=0;c<16;c++)
            for(int v=0;v<16;v++)
            if(puzzle[r][c]=='-'||puzzle[r][c]=='A'+v)//  ，      v       
        {
            vector<int>columns;  //            
            columns.push_back(encode(SLOT,r,c));
            columns.push_back(encode(ROW,r,v));
            columns.push_back(encode(COL,c,v));
            columns.push_back(encode(SUB,(r/4)*4+c/4,v));//(r,c)          (r/4)*4+c/4
            solver.addRow(encode(r,c,v),columns);
        }

        vector<int>ans;
        assert(solver.solve(ans));

        for(int i=0;i<ans.size();i++)
        {
            int r,c,v;
            decode(ans[i],r,c,v);
            puzzle[r][c]='A'+v;
        }
        for(int i=0;i<16;i++)
            printf("%s
",puzzle[i]);
    }
}