글 읽기 - 반례좀 찾아주세요..

mhs4670 6년 전 0

저는 우선 6개 줄에 있는 총 24개의 점을(물론 겹치지만) dfs로 배정한다음에

거기서 제일 사전순으로 빠른 것을 구했는데요;;

자꾸 틀리더라구요 ㅠㅠ

원문으로 가서 공개된 테스트케이스를 모두 돌려봤는데 다 맞았는데.....

제출하면 틀려요 ㅠㅠ

어떤 반례가 있는걸까요 흑흑

#include<stdio.h>
#include<string.h>

char star[5][10];
int lineY[24] = { 0, 1, 2, 3, 3, 3, 3, 3, 3, 2, 1, 0,
1, 2, 3, 4, 4, 3, 2, 1, 1, 1, 1, 1 };
int lineX[24] = { 4, 3, 2, 1, 1, 3, 5, 7, 7, 6, 5, 4, 1, 2, 3, 4,
4, 5, 6, 7, 7, 5, 3, 1 };
int solY[12] = { 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4 };
int solX[12] = { 4, 1, 3, 5, 7, 2, 6, 1, 3, 5, 7, 4 };
char min[13];
char temp[13];
int visit[13];
void input(void){
	int i, j;
	for (i = 0; i < 5; i++){
		scanf("%s", star[i]);
	}
	for (i = 0; i < 12; i++){
		if (star[solY[i]][solX[i]] != 'x'){
			visit[star[solY[i]][solX[i]] - 'A' + 1] = 1;
		}
	}
}
void set(void){ //맨 처음부터 3개가 있다면, 배정해주기
	int i, j;
	int cnt;
	int sum, t;
	for (i = 0; i < 24; i += 4){
		sum = cnt = 0;
		for (j = 0; j < 4; j++){
			if (star[lineY[i + j]][lineX[i + j]] != 'x'){
				cnt++; sum += (star[lineY[i + j]][lineX[i + j]] - 'A' + 1);
			}
			else{
				t = i + j;
			}
		}
		if (cnt == 3){
			star[lineY[t]][lineX[t]] = 26 - sum - 1 + 'A';
			visit[26 - sum] = 1;
		}
	}
}
void dfs(int L, int sum){
	int i;
	if (!(L % 4)){
		if (sum % 26) return;
	}
	if (L >= 24){
		for (int i = 0; i < 12; i++){
			temp[i] = star[solY[i]][solX[i]];
		}
		temp[12] = 0;
		if (strcmp(min, temp) == 1){
			for (int i = 0; i < 12; i++){
				min[i] = temp[i];
			}
		}
		return;
	}
	if (star[lineY[L]][lineX[L]] != 'x'){
		dfs(L + 1, sum + (star[lineY[L]][lineX[L]] - 'A' + 1));
		return;
	}
	for (i = 1; i <= 12; i++){
		if (visit[i]) continue;
		star[lineY[L]][lineX[L]] = i - 1 + 'A'; visit[i] = 1;
		dfs(L + 1, sum + i);
		visit[i] = 0; star[lineY[L]][lineX[L]] = 'x';
	}
}
int main(void){

	for (int i = 0; i < 12; i++){
		min[i] = 'Z';
	}
	input();
	set();
	dfs(0, 0);
	for (int i = 0; i < 12; i++){
		star[solY[i]][solX[i]] = min[i];
	}
	for (int i = 0; i < 5; i++){
		printf("%s\n", star[i]);
	}
	return 0;
}

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

문제

문제

출처

ICPC

반례좀 찾아주세요..

mhs4670 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말