글 읽기 - 반례 부탁드립니다(C++)

kiyaaa 2년 전 0

못찾고 있습니다.

헬프 요청합니다...

#include <stdio.h>
#define MAX 100000


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

int hy[8] = { 2,2,1,1,-1,-1,-2,-2 };
int hx[8] = { -1,1,-2,2,-2,2,-1,1 };


struct Node {
	int y;
	int x;
	int height;
	int count;
};

Node queue[MAX];

int K;
int xSize, ySize;
int map[201][201];
bool visit[201][201];
int head, tail;

//void enqueue(int y, int x, int height, int count) {
void enqueue(int y, int x, int count) {
	head = (head + 1) % MAX;
	queue[head].y = y;
	queue[head].x = x;
	//queue[head].height = height;
	queue[head].count = count;
}

Node* dequeue() {

	tail = (tail + 1) % MAX;

	return &queue[tail];
}


int main() {
	scanf("%d", &K);
	scanf("%d %d", &xSize, &ySize);

	for (int i = 0; i < ySize; i++) {
		for (int j = 0; j < xSize; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	//enqueue(0, 0, 0, 0);
	enqueue(0, 0, 0);

	while (head != tail) {
		Node* node = dequeue();
		register int y = node->y;
		register int x = node->x;
		//register int height = node->height;
		register int count = node->count;

		if (y == ySize - 1 && x == xSize - 1) {
			printf("%d\n", count);
			return 0;
		}

		if (count < K) {
			for (int i = 0; i < 8; i++) {
				int ny = y + hy[i];
				int nx = x + hx[i];
				if (0 <= ny && 0 <= nx && ny <= ySize - 1 && nx <= xSize - 1 && !map[ny][nx] && !visit[ny][nx]) {
					visit[ny][nx] = true;
					enqueue(ny, nx, count + 1);
				}
			}
		}
		else {
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (0 <= ny && 0 <= nx && ny <= ySize - 1 && nx <= xSize - 1 && !map[ny][nx] && !visit[ny][nx]) {
					visit[ny][nx] = true;
					enqueue(ny, nx, count + 1);
				}
			}
		}
	}

	printf("-1");

	return 0;
}

kiyaaa 2년 전 0

아 이게 처음부터 K번 말처럼 움직이는 게 아니라

움직이는 중에 K번 아무때나 말처럼 움직이는 거였네요..

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

문제

문제

출처

ICPC

반례 부탁드립니다(C++)

kiyaaa 2년 전 0

kiyaaa 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말