글 읽기 - 반례를 못 찾겠습니다.

rlasoaen 4년 전 0

int dp[ y좌표 ][ x좌표 ][ 방향 ][ 배달 상태 ] 로 정의하고 시간을 담았습니다.

배달 상태는 다음과 같이 정의하고 3이 되면 시간을 반환하도록 하였습니다.

0 -> 아무 곳도 배달하지 못 함

1 -> 1번째 C에 배달 완료

2 -> 2번째 C에 배달 완료

3 -> 배달 모두 완료

예제나 질문 검색에 있는 반례는 모두 통과하는데 어디서 문제가 생긴지 모르겠네요.

도움 부탁드립니다.

#include <iostream>
#include <queue>

using namespace std;

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

int N, M;
char map[50][50];

int minY, minX;
int c1Y, c1X;
int c2Y, c2X;
int dp[50][50][4][4];

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		cin >> map[i];
	}
}

void init() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			for (int k = 0; k < 4; ++k) {
				for (int l = 0; l < 4; ++l) {
					dp[i][j][k][l] = 987654321;
				}
			}
		}
	}
}

void getStartGoal() {
	int cnt = 0;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (map[i][j] == 'S') {
				minY = i;
				minX = j;
			}
			if (map[i][j] == 'C') {
				++cnt;
				if (cnt == 1) {
					c1Y = i;
					c1X = j;
				}
				if (cnt == 2) {
					c2Y = i;
					c2X = j;
				}
			}
		}
	}

}

int bfs() {
	queue<int> yq, xq, tq, dq, cq;

	yq.push(minY);
	xq.push(minX);
	tq.push(0);
	cq.push(0);
	dq.push(4);

	while (!yq.empty())
	{
		int y = yq.front();
		int x = xq.front();
		int time = tq.front();
		int count = cq.front();
		int direction = dq.front();
		yq.pop(), xq.pop(), tq.pop(), cq.pop(), dq.pop();
		//cout << y << ", " << x << " / time : " << time << " / count : " << count << endl;
		
		if (count == 3) {
			return (time);
		}

		for (int i = 0; i < 4; ++i) {
			if (direction == i) continue;

			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (map[ny][nx] == '#') continue;
			if (time + 1 >= dp[ny][nx][i][count]) continue;
		
			dp[ny][nx][i][count] = time + 1;
			yq.push(ny);
			xq.push(nx);
			tq.push(time + 1);
			dq.push(i);

			if (ny == c1Y && nx == c1X)
					cq.push(count | 1);
			else if (ny == c2Y && nx == c2X)
					cq.push(count | 2);
			else
				cq.push(count);
		}
	}
	return (-1);
}

int solve() {
	int answer;

	init();
	getStartGoal();
	answer = bfs();
	return (answer);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	input();
	cout << solve();
	return (0);
}

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다.

rlasoaen 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말