태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          

Notice

2011.08.11 20:04 Solutions/Dlbo's Solution
아 나

스도쿠 한번 풀기 더럽게 빡치네

이게 얼마나 걸린거야 -_- 
#include 
#include 

#define SIBAL 750
#define CIBAL 350
#define V SIBAL*CIBAL

int U[V], D[V];
int L[V], R[V];
int C[V], ROW[V];
int H[SIBAL], S[CIBAL];
int size;
char s[10][10];
int nimiral1[SIBAL], nimiral2[SIBAL], OK[87];
char nimhi[SIBAL];

void Link(int r, int c)
{
    S[c]++ ;
	C[size] = c;
    ROW[size] = r;
    U[size] = U[c];
	D[U[c]] = size;
    D[size] = c;
	U[c] = size;

    if (H[r] ==  - 1)
	{
		H[r] = L[size] = R[size] = size;
	}
    else
    {
        L[size] = L[H[r]];
		R[L[H[r]]] = size;
        R[size] = H[r];
		L[H[r]] = size;
    }

    size++ ;
}

void remove(int c)
{
    int i, j;

    L[R[c]] = L[c];
    R[L[c]] = R[c];

    for (i = D[c]; i != c; i = D[i])
    {
        for (j = R[i]; j != i; j = R[j])
        {
            S[C[j]]-- ;
            U[D[j]] = U[j];
            D[U[j]] = D[j];
        }
    }
}

void resume(int c)
{
    int i, j;

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

    R[L[c]] = L[R[c]] = c;
}

int Jotto(int k)
{
    int i, j, Min, c;

    if (!R[0])
	{
		return 1;
	}

    for (Min = SIBAL, i = R[0]; i; i = R[i])
	{
		if (Min > S[i])
		{
			Min = S[i];
			c = i;
		}
	}

    remove(c);

    for (i = D[c]; i != c; i = D[i])
    {
        for (j = R[i]; j != i; j = R[j])
		{
            remove(C[j]);
		}

        OK[k] = ROW[i];

        if (Jotto(k + 1))
		{
			return 1;
		}

        for (j = L[i]; j != i; j = L[j])
		{
            resume(C[j]);
		}
    }

    resume(c);
    return 0;
}

int main()
{
    int i, j, k, r;
    char st[87];

    while (gets(st))
    {
		if (st[0] == 'e')
		{
			break;
		}

        i = 0;

        for (j = 1; j <= 9; j++)
		{
            for (k = 1; k <= 9; k++)
			{
                s[j][k] = st[i++];
			}
		}
        for (i = 0; i <= 324; i++)
        {
            S[i] = 0;
            D[i] = U[i] = i;
            L[i + 1] = i;
			R[i] = i + 1;
        }

		R[324] = 0;
        size = 325;
        r = 0;
        memset(H,  - 1, sizeof(H));

        for (i = 1; i <= 9; i++)
        {
            for (j = 1; j <= 9; j++)
            {
                if (s[i][j] != '.')
                {
                    r++ ;
                    nimiral1[r] = i;
                    nimiral2[r] = j;
                    nimhi[r] = s[i][j];
                    Link(r, (i - 1)*9 + j);
                    Link(r, 81 + (i - 1)*9 + s[i][j] - '0');
                    Link(r, 162 + (j - 1)*9 + s[i][j] - '0');
                    Link(r, 243 + ((i - 1)/3)*27  + ((j - 1)/3)*9  + s[i][j] - '0');    
                }
                else 
                {
                    for (k = 1; k <= 9; k++)
                    {
                        r++ ;
                        nimiral1[r] = i;
                        nimiral2[r] = j;
                        nimhi[r] = k + '0';
                        Link(r, (i - 1)*9 + j);
                        Link(r, 81 + (i - 1)*9 + k);
                        Link(r, 162 + (j - 1)*9 + k);
                        Link(r, 243 + ((i - 1)/3)*27  + ((j - 1)/3)*9  + k );        
                    }
                }
            }
        }

        Jotto(0);

        for (i = 0; i<81; i++)
		{
            s[nimiral1[OK[i]]][nimiral2[OK[i]]] = nimhi[OK[i]];
		}
        for (i = 1; i<= 9; i++)
		{
            for (j = 1; j <= 9; j++)
			{
                printf("%d", s[i][j] - '0');
			}
		}
        puts("");
    }

    return 0;
}
지금쯤 훈련소를 나왔을 지군에게 이 코드를 바침 -_-
posted by Lonewolf dlbo
TAG

댓글을 달아 주세요

  1. zz 난 당장은 모르겠고

    이번달 안에 풀어보도록 노력하겠음 ㅋㅋㅋㅋ