글 읽기 - 시간초과가 납니다..

draner11 7년 전 0

hole을 저장해놓고

hole일경우 가로 세로 9방향 한번에 검사했습니다..

왜 시간 초과일까요...

1%도 못넘습니다..

#include <cstdio>
#include <cstring>
#define MAX 9
using namespace std;
int arr[MAX][MAX];
typedef struct point{
	int x; int y;
}Point;
bool num[MAX + 1];
bool num1[MAX + 1];
bool num2[MAX + 1];
Point hole[81]; 
int rear;
int holeCnt;
int cnt,cnt1,cnt2;
int dx[9] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };
int dy[9] = { -1, -1, -1, 0, 0, 0, 1, 1, 1 };
Point p[9];

void solve(int x, int y){
	int centerx = p[x / 3].x;
	int centery = p[y / 3].y;
	int tx, ty;
	cnt =cnt1=cnt2= 0;
	memset(num, false, sizeof(bool)*(MAX + 1));
	memset(num1, false, sizeof(bool)*(MAX + 1));
	memset(num2, false, sizeof(bool)*(MAX + 1));

	for (int i = 0;i < 9; i++)
	{
		if (!num1[arr[x][i] ])
		{
			num1[arr[x][i]] = true;	cnt1 += 1;
		}
		if (!num2[arr[i][y]])
		{
			num2[arr[i][y]] = true;	cnt2 += 1;
		}

		tx = centerx + dx[i];
		ty = centery + dy[i];
		if (!num[arr[tx][ty]])
		{
			num[arr[tx][ty]] = true;
			cnt += 1;
		}
			
	}

	for (int j = 0; j < MAX+1 ; j++){
		if (!num1[j] && cnt1 == MAX){
			arr[x][y] = j;	holeCnt -= 1;
			break;
		}
		if (!num2[j] && cnt2 == MAX){
			arr[x][y] = j;	holeCnt -= 1;
			break;
		}
		if (!num[j] && cnt == MAX){
			arr[x][y] = j;	holeCnt -= 1;
			break;
		}
	}


}


int main(){
	p[0].x = 1; 	p[0].y = 1;
	p[1].x = 4; 	p[1].y = 4;
	p[2].x = 7; 	p[2].y = 7;

	for (int i = 0; i < MAX; i++){
		for (int j = 0; j < MAX; j++)
		{
			scanf("%d", &arr[i][j]);
			if (arr[i][j] == 0){		
				hole[rear].x = i;
				hole[rear++].y = j;
			
			}
		}
	}
	holeCnt = rear;

	while (holeCnt)
	{
		for (int i = 0; i < rear; i++){		
			if (arr[hole[i].x][hole[i].y] == 0){//홀이라면
				solve(hole[i].x, hole[i].y);	
			}		
		}
	}
	
	for (int i = 0; i < MAX; i++){
		for (int j = 0; j < MAX - 1; j++){
			printf("%d ", arr[i][j]);
		}
		printf("%d\n", arr[i][MAX - 1]);

	}
	return 0;
}

ntopia 7년 전 2

저렇게 단순한 추론만 반복하게 되면

어려운 퍼즐의 경우에는 holeCnt 가 전혀 줄어들지 않은 채로 무한히 루프를 반복하게 됩니다

추론 규칙을 빡세게 구현하시든지, 아니면 백트래킹으로 찍어볼 수 밖에 없습니다

아래와 같은 데이터를 넣어보세요

0 0 0 0 0 0 0 0
0 3 6 0 0 0 0 0
7 0 0 9 0 2 0 0
5 0 0 0 7 0 0 0
0 0 0 4 5 7 0 0
0 0 1 0 0 0 3 0
0 1 0 0 0 0 6 8
0 8 5 0 0 0 1 0
9 0 0 0 0 4 0 0

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

문제

문제

출처

ICPC

시간초과가 납니다..

draner11 7년 전 0

ntopia 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말