글 읽기 - 스페셜 저지 추가해주세요.

zych1751 6년 전 0

맞왜틀!!!

데이터를 찾아 돌려봤는데 실제 정답과 다르긴 한데 스도쿠판은 잘 만들어진것 같습니다.

스페셜저지를 추가해서 제 맞왜틀을 증명해주세요.

홍준님 문제집 깨고싶어요 ㅠㅠ

#include<bits/stdc++.h>

using namespace std;

bool row[6][10], col[6][10], sq[6][10];
int num[6][6][2];
char str[4];
int ch[256];

void init()
{
	memset(row, 0, sizeof(row));
	memset(col, 0, sizeof(col));
	memset(sq, 0, sizeof(sq));
}

int sq_num(int i, int j)
{
	return (i/2)*2 + j/3;
}

void add(int i, int j, int k, int val)
{
	num[i][j][k] = val;
	row[i][val] = true;
	col[j][val] = true;
	sq[sq_num(i, j)][val] = true;
}

void del(int i, int j, int k)
{
	int val = num[i][j][k];
	row[i][val] = false;
	col[j][val] = false;
	sq[sq_num(i, j)][val] = false;
	num[i][j][k] = 0;
}

bool dfs(int i, int j, int k)
{
	if(k == 2)	return dfs(i, j+1, 0);
	if(j == 6)	return dfs(i+1, 0, k);
	if(i == 6)	return true;

	if(num[i][j][k] != 0)
		return dfs(i, j, k+1);

	for(int v = (k==0?1:num[i][j][0]+1); v <= 9; v++)
	{
		if(row[i][v] || col[j][v] || sq[sq_num(i, j)][v])	continue;

		add(i, j, k, v);
		if(dfs(i, j, k+1))
			return true;
		del(i, j, k);
	}
	return false;
}

bool check()
{
	for(int i = 0; i < 6; i++)
	{
		int check[10] = {0, };
		for(int j = 0; j < 6; j++) 
			for(int k = 0; k < 2; k++)
				if(num[i][j][k] != -1)
					check[num[i][j][k]]++;
		for(int k = 1; k <= 9; k++)
			if(check[k] != 1)
				return false;
	}
	for(int i = 0; i < 6; i++)
	{
		int check[10] = {0, };
		for(int j = 0; j < 6; j++) 
			for(int k = 0; k < 2; k++)
				if(num[j][i][k] != -1)
					check[num[j][i][k]]++;
		for(int k = 1; k <= 9; k++)
			if(check[k] != 1)
				return false;
	}
	for(int sq = 0; sq < 6; sq++)
	{
		int check[10] = {0, };
		for(int i = (sq/2*2); i < sq/2*2+2; i++) 
			for(int j = (sq%2==0?0:3); j < (sq%2==0?3:6); j++)
				for(int k = 0; k < 2; k++)
					if(num[i][j][k] != -1)
						check[num[i][j][k]]++;
		for(int k = 1; k <= 9; k++)
			if(check[k] != 1)
				return false;
	}
	return true;
}

int main()
{
	for(int i = 1; i <= 9; i++)
		ch[i+'0'] = i;
	ch['-'] = 0;

	int tcc;
	scanf("%d", &tcc);
	for(int tc = 1; tc <= tcc; tc++)
	{
		init();

		int k;
		scanf("%d", &k);
		printf("%d\n", k);

		for(int i = 0; i < 6; i++)
			for(int j = 0; j < 6; j++)
			{
				scanf("%s", str);
				if(strlen(str) == 3)
				{
					add(i, j, 0, ch[str[0]]);
					add(i, j, 1, ch[str[2]]);
				}
				else
				{
					add(i, j, 0, ch[str[0]]);
					num[i][j][1] = -1;
				}
			}
		dfs(0, 0, 0);

		for(int i = 0; i < 6; i++)
		{
			for(int j = 0; j < 6; j++)
			{
				printf("%d", num[i][j][0]);
				if(num[i][j][1] != -1)
					printf("/%d", num[i][j][1]);
				if(j != 5)
					printf(" ");
			}
			printf("\n");
		}
		assert(check());
	}
	return 0;
}

doju 6년 전 1

데이터를 돌려 봤는데 The smaller number always goes above the slash. 에 위배되는 답을 출력하고 있습니다.

놀랍게도 공식 데이터의 모든 테스트 케이스는 답이 유일합니다.

h0ngjun7 6년 전 2

본 문제는 답이 유일합니다.

왜냐하면 제 코드가 가능한 보드판을 모두 출력하는 코드이기 때문입니다.

h0ngjun7 6년 전 0

앗 doju님이 답글 먼저 다셧네요ㅠ

zych1751 6년 전 1

오오 다들 감사합니다.

그 조건을 처리한줄 알았는데 덜 처리했었네요.

덕분에 홍준님 문제집 하나 클리어 했습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

스페셜 저지 추가해주세요.

zych1751 6년 전 0

doju 6년 전 1

h0ngjun7 6년 전 2

h0ngjun7 6년 전 0

zych1751 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말