태터데스크 관리자

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

태터데스크 메시지

저장하였습니다.
블로그 이미지
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 31      

Notice

'2011/08'에 해당되는 글 2

  1. 2011.08.12 PKU 3074. Sudoku. [판정:TLE](1)
  2. 2011.08.11 PKU 3074. Sudoku. AC get -_-(1)
2011.08.12 13:54 Solutions/Mr.K's Solution
ㅋㅋㅋ

너무 정석대로 풀었나
뭔가 빨리 돌리는 방법이 있을텐뎈ㅋ


#include 
using namespace std;

void zeroset( int ary[][9] );
int numfind( int ary[][9], int bry[][9], int wtf );

int find[10]; // 숫자 k(k번째 원소)를 몇개나 찾았는가에 해당하는 배열

int main()
{
	char str[90];
	int a[9][9]; // 풀어야되는 스도쿠
	int b[9][9]; // 메모지
	int i, j;
	int temp;

	while(1)
	{
		gets(str);

		if( strcmp( str, "end" ) == 0 )
		{
			break;
		}

		for( i = 0; i <= 9; i++ )
		{
			find[i] = 0;
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				if( str[i*9+j] == '.' )
				{
					a[i][j] = 0;
				}
				else
				{
					a[i][j] = str[i*9+j] - '0';
					find[a[i][j]]++;
					find[0]++;
				}
			}
		}

		while( find[0] < 81 )
		{
			// 스도쿠 연산
			for( i = 1; i <= 9; i++ )
			{
				zeroset( b );
				for( j = 0; j < 2; j++ )
				{
					if( find[i] < 9 )
					{
						temp = numfind( a, b, i );
					}
					if( temp == 0 )
					{
						// 찾는 숫자가 없거나 숫자 대입을 하지 않았으면 함수를 2번 돌릴 필요가 없음
						j++;
					}
				}
			}
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				printf( "%d", a[i][j] );
			}
		}
		printf("\n");
	}

	return 0;
}

void zeroset( int ary[][9] )
{
	int i, j;

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			ary[i][j] = 0;
		}
	}
}

int numfind( int ary[][9], int bry[][9], int wtf ) // wtf : isn't what the fu*k, want to find
{
	int i, j, k, m;
	int esc = 1;
	int count;
	int tempr, tempc;

	// wtf 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] == wtf )
			{
				bry[i][j] = 2;
				esc = 0;
			}
		}
	}

	// wtf가 현재 스도쿠에 없음
	if( esc == 1 )
	{
		return 0;
	}

	// wtf가 위치할 수 없는 범위 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( bry[i][j] == 2 )
			{
				for( k = 0; k < 9; k++ )
				{
					bry[i][k] = 1;
					bry[k][j] = 1;
				}
				for( k = (i/3)*3; k < (i/3)*3+3; k++ )
				{
					for( m = (j/3)*3; m < (j/3)*3+3; m++ )
					{
						bry[k][m] = 1;
					}
				}

				bry[i][j] = 2;
			}
		}
	}

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] != 0 && bry[i][j] == 0 )
			{
				bry[i][j] = 1;
			}
		}
	}

	// wtf가 유일하게 들어갈 수 있으면 대입
	for( i = 0; i < 3; i++ )
	{
		for( j = 0; j < 3; j++ )
		{
			count = 0;
			for( k = i*3; k < (i+1)*3; k++ )
			{
				for( m = j*3; m < (j+1)*3; m++ )
				{
					if( bry[k][m] == 0 )
					{
						tempr = k;
						tempc = m;
						count++;
					}
				}
			}

			if( count == 1 )
			{
				ary[tempr][tempc] = wtf;
				find[wtf]++;
				find[0]++;
				esc = 1;
			}
		}
	}

	return esc;
}
 
posted by Milkskin
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 스도쿠
prev 1 next