글 읽기 - 97%에서 틀렸다고 하는데 어떤 경우가 예외처리가 안됬는지 모르겠습니다.

scared22 5년 전 0

나이트의 이동경로를 bfs탐색 구현했습니다. 97%에서 틀렸다고 하는데 어떤경우에 오답인지 알고 싶습니다.

도와주세요 ㅜㅜ

#include <iostream>
#include <queue>

using namespace std;

int check[10][10];
int dy[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
int dx[] = { -1, 1, -2, 2, -2, 2, -1, 1 };

struct data
{
	int y, x;
};

queue < data > q;

int main()
{
	int ey, ex, sy, sx;

	for (int i = 0; i < 36; i++)
	{
		int y;
		char x;

		cin >> x >> y;

		if (i == 0)
		{
			ey = y, ex = x - 64;
			sy = y, sx = x - 64;
		}

		else q.push({ y, x - 64 });
	}

	q.push({ ey, ex });

	while (!q.empty())
	{
		int cy = q.front().y;
		int cx = q.front().x;
		q.pop();

		bool judge = false;

		for (int i = 0; i < 8; i++)
		{
			int dposy = sy + dy[i];
			int dposx = sx + dx[i];

			if (dposy < 1 || dposy > 6 || dposx < 1 || dposx > 6 || check[dposy][dposx]) continue;

			if (dposy == cy && dposx == cx)
			{
				judge = true;
				check[cy][cx] = 1;
				sy = cy, sx = cx;
				break;
			}
		}

		if (!judge) break;

		if (sy == ey && sx == ex)
		{
			cout << "Valid" << "\n";
			return 0;
		}

	}

	cout << "Invalid" << "\n";

	return 0;
}

djm03178 5년 전 0

지금 테스트는 못 해보겠지만, 경로 중간에 시작점을 또 방문하게 하면 어떻게 되나요?

scared22 5년 전 0

아 그것은 생각을 해보지 않았네요

scared22 5년 전 0

고맙습니다 덕분에 해결됬습니다 엄청난 힌트 주셔서 감사합니다 .

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

문제

문제

출처

ICPC

97%에서 틀렸다고 하는데 어떤 경우가 예외처리가 안됬는지 모르겠습니다.

scared22 5년 전 0

djm03178 5년 전 0

scared22 5년 전 0

scared22 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말