글 읽기 - 오답케이스 부탁 드립니다.(솔루션 공유)

na982 8년 전 0

A, B, C 물통에 물을 규칙대로 옮겨 가면서 bfs 로 모든경우를 순회하고, 이미 예전에 했던 케이스는 제외 하는 방식으로 진행하였는데, 오답이네요.

x -> C 로 옮기는 경우는 항상 넘치는 경우가 없기 때문에, 이부분 처리했습니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef struct {
	int A, B, C;
}DATA;

int visited[201][201][201];

void push_data(queue<DATA>& q, DATA& data) {
	if (visited[data.A][data.B][data.C] == -1) {
		q.push(data);
		visited[data.A][data.B][data.C] = 1;
	}
}

int main()
{
	DATA data;
	scanf("%d %d %d", &data.A, &data.B, &data.C);
	memset(visited, -1, sizeof(visited));
	vector<int> result;
	queue<DATA> q;
	DATA cur;
	cur.A = 0, cur.B = 0, cur.C = data.C;
	q.push(cur);
	visited[cur.A][cur.B][cur.C] = 1;
	
	while (!q.empty()) {
		cur = q.front();
		q.pop();
		if (cur.A == 0) {
			result.push_back(cur.C);
		}

		DATA next;
		//A -> B
		next.A = 0;
		next.B = cur.B + cur.A;
		next.C = cur.C;
		if (next.B > data.B) {
			next.A += next.B - data.B;
			next.B = data.B;
		}
		push_data(q, next);
		//A -> B -> C
		next.A = 0;
		next.B = cur.B + cur.A;
		next.C = cur.C;
		if (next.B > data.B) {
			next.C += next.B - data.B;
			next.B = data.B;
		}
		push_data(q, next);
		//A -> C
		next.A = 0;
		next.B = cur.B;
		next.C = cur.C + cur.A;
		push_data(q, next);

		//B -> A
		next.A = cur.A + cur.B;
		next.B = 0;
		next.C = cur.C;
		if (next.A > data.A) {
			next.B += next.A - data.A;
			next.A = data.A;
		}
		push_data(q, next);
		//B -> A -> C
		next.A = cur.A + cur.B;
		next.B = 0;
		next.C = cur.C;
		if (next.A > data.A) {
			next.C += next.A - data.A;
			next.A = data.A;
		}
		push_data(q, next);
		//B -> C
		next.A = cur.A;
		next.B = 0;
		next.C = cur.C + cur.B;
		push_data(q, next);

		//C -> A
		next.A = cur.A + cur.C;
		next.B = cur.B;
		next.C = 0;
		if (next.A > data.A) {
			next.C += next.A - data.A;
			next.A = data.A;
		}
		push_data(q, next);
		//C -> A -> B
		next.A = cur.A + cur.C;
		next.B = cur.B;
		next.C = 0;
		if (next.A > data.A) {
			next.B += next.A - data.A;
			next.A = data.A;
		}
		push_data(q, next);
		//C -> B
		next.A = cur.A;
		next.B = cur.B + cur.C;
		next.C = 0;
		if (next.B > data.B) {
			next.C += next.B - data.B;
			next.B = data.B;
		}
		push_data(q, next);
		//C -> B -> A
		next.A = cur.A;
		next.B = cur.B + cur.C;
		next.C = 0;
		if (next.B > data.B) {
			next.A += next.B - data.B;
			next.B = data.B;
		}
		push_data(q, next);
	}

	sort(result.begin(), result.end());

	for (int i = 0; i < result.size(); ++i) {
		printf("%d ", result[i]);
	}
	printf("\n");

	return 0;
}

na982 8년 전 0

A물을 B로 옮기고 넘치는 양을 C로 옮기는 경우,

C도 넘치는 경우가 빠졌네요; C도 넘치면 다시 A에 넣을수 있도록 수정하여 억셉 받았습니다.

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

문제

문제

출처

ICPC

오답케이스 부탁 드립니다.(솔루션 공유)

na982 8년 전 0

na982 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말