글 읽기 - 반례를 찾을 수가 없습니다.

wldnjs95 6년 전 0

예제 입력도 다 맞고 다른 케이스들도 확인해봤는데 반례를 못찾겠네요ㅜㅜ

#include <stdio.h>
//#define p 5
//#define q 5

typedef struct point {
	char x;
	int y;
}point;

point pts[30];

int np;
int cnt;
int chess[30][30];
char alp[28] = {0,0,'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };
int di[8] = {-2,-2,-1,1,2,2,1,-1};
int dj[8] = {-1,1,2,2,1,-1,-2,-2};
int flag = 0;
void knight(int r, int c) {
	int dir,i, j;
	if (flag == 1) return;
	pts[cnt-1].x = alp[c];
	pts[cnt - 1].y = r - 1;
	
	if (cnt == np) {
		flag = 1;
		for (i = 0; i < np; i++) {
			printf("%c%d", pts[i].x, pts[i].y);
		}
		printf("\n");
		return;
	}

	for (dir = 0; dir < 8; dir++) {
		i = r + di[dir];
		j = c + dj[dir];
		if (chess[i][j] == 0 && flag==0) {
			cnt++;
			chess[i][j] = 1;
			knight(i, j);
			chess[i][j] = 0;
			cnt--;
		}
	}

}

int main(void) {

	int i, j,k=0;
	int p, q;
	int Case;
	scanf("%d", &Case);


	while (Case > 0) {
		flag = 0;
		scanf("%d %d", &p, &q);
		np = p*q;
		printf("Scenario #%d:\n", ++k);
		for (i = 0; i < 30; i++) {
			for (j = 0; j < 30; j++) {
				chess[i][j] = -1;
			}
		}


	for (i = 2; i < 2 + p; i++) {
		for (j = 2; j < 2 + q; j++) {
			chess[i][j] = 0;
		}
	}

	for (i = 2; i < 2 + p; i++) {
		for (j = 2; j < 2 + q; j++) {
			cnt = 1;
			chess[i][j] = 1;
			knight(i, j);
			chess[i][j] = 0;
			if (flag == 1) break;
		}
		if (flag == 1) break;
	}
	if (flag == 0) printf("impossible\n");
	Case--;
	}
	return 0;
}

kdk8361 6년 전 1

1
5 4
Scenario #1:
A1B3A5C4D2B1A3B5D4C2B4A2C1D3C5A4B2D1C3D5

가 출력되어야 하는데

A1C2D4B5A3B1D2C4A5B3C1D3C5A4B2D1C3D5B4A2

를 출력하시네요. 조건을 다시한번 잘 살펴보시면 될 것 같습니다.

wldnjs95 6년 전 0

아 저는 가능한 케이스 아무거나 출력하는지 알았는데

lexicographically 라는 조건을 놓쳤네요

해결했어요 감사합니다!

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

문제

문제

출처

ICPC

반례를 찾을 수가 없습니다.

wldnjs95 6년 전 0

kdk8361 6년 전 1

wldnjs95 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말