글 읽기 - 혹시 이 문제 풀이가 이게 아닌가요?

kinssang 6년 전 0

보드의 크기가 4*5로 고정이라는 점. 재방문은 가능하나, 처음 방문할 시엔 순서를 맞춰야하고, 최소의 이동거리를 구한다는 점에 착안해서

BFS + 비트마스크로 풀었습니다

근데 33%에서 틀렸습니다가 뜨네요.

미쳐 고려하지 못한 코너케이스가 있는지, 아니면 아예 풀이를 잘못한건지... 도움 요청드립니다.

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

bool memo[1048576][4][5];
int dr[4] = { 1, 0, -1, 0 };
int dc[4] = { 0, 1, 0, -1 };

struct point
{
	int r;
	int c;
	int move;
	int visit;
	int last;
};

int val(char ch)
{
	if (ch >= '0' && ch <= '9') return ch - '0';
	else return ch - 'A' + 10;
}

int main()
{
	freopen("input.txt", "r", stdin);

	int T;

	scanf("%d", &T);

	for (int testcase = 0; testcase < T; testcase++)
	{
		memset(memo, 0, sizeof(memo));

		char board[4][6] = {};
		int end = 0, start_r, start_c;
		bool Can = false;

		for (int i = 0; i < 4; i++)
		{
			scanf("%s", board[i]);
			for (int j = 0; j < 5; j++)
			{
				if(board[i][j] != '.') end |= (1 << (5 * i + j));
				if (board[i][j] == '0')
				{
					start_r = i;
					start_c = j;
				}
			}
		}

		std::queue<point> q;
		q.push({ start_r, start_c, 0, 1 << (5*start_r+start_c), 0});
		memo[1 << (5 * start_r + start_c)][start_r][start_c] = true;

		while (!q.empty())
		{
			int r = q.front().r, c = q.front().c, move = q.front().move, visit = q.front().visit, last = q.front().last;
			q.pop();
			if (visit == end)
			{
				Can = true;
				printf("%d\n", move);
				break;
			}
			for (int i = 0; i < 4; i++)
			{
				int new_r = r + dr[i], new_c = c + dc[i];
				if (new_r < 0 || new_r >= 4 || new_c < 0 || new_c >= 5) continue;
				if (board[new_r][new_c] == '.') continue;
				if (board[new_r][new_c] != '#' && val(board[new_r][new_c]) > last + 1) continue;
				if (memo[visit | (1 << (5 * new_r + new_c))][new_r][new_c]) continue;
				memo[visit | (1 << (5 * new_r + new_c))][new_r][new_c] = true;
				if(board[new_r][new_c] == '#') q.push({ new_r, new_c, move + 1, visit | (1 << (5 * new_r + new_c)), last});
				else q.push({ new_r, new_c, move + 1, visit | (1 << (5 * new_r + new_c)), std::max(val(board[new_r][new_c]), last) });
			}
		}
		if (!Can) printf("-1\n");
	}
	return 0;
}

kinssang 6년 전 0

오늘의 교훈 : 제발 제출할 때 freopen을 빼자

끄읏

jh05013 6년 전 1

온라인 저지들이 -DONLINE_JUDGE를 컴파일 옵션에 넣는다는 점을 이용하면 freopen을 안 빼고 제출할 수도 있습니다.

int main()
{
    #ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
    #endif
}

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

문제

문제

출처

ICPC

혹시 이 문제 풀이가 이게 아닌가요?

kinssang 6년 전 0

kinssang 6년 전 0

jh05013 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말