글 읽기 - 2251 물통 반례 있으신분 계신가요..?

ojh4110 5년 전 0

아무리 봐도 맞은거 같은데 혹시 반례 나 틀린부분 지적해 주실분 계신가요 ㅠㅠ?

도와주십쇼!

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>

using namespace std;

map<int, int> visit;

int a_max, b_max, c_max;

struct state {
    int a;
    int b;
    int c;
    state(int a, int b, int c) : a(a), b(b), c(c) {}

};


int getRemain(state state1, char taker) {
    switch (taker) {
        case 'a':
            return a_max - state1.a;
        case 'b':
            return b_max - state1.b;
        case 'c':
            return c_max - state1.c;
        default:
            break;
    }
}

int getShouldGive(state state1, char giver) {
    switch (giver) {
        case 'a':
            return state1.a;
        case 'b':
            return state1.b;
        case 'c':
            return state1.c;
        default:
            break;
    }
}

state give(state state1, char giver, char taker, int amount) {
    state result = state1;
    switch (giver) {
        case 'a':
            result.a -= amount;
            break;
        case 'b':
            result.b -= amount;
            break;
        case 'c':
            result.c -= amount;
            break;

        default:
            break;
    }
    switch (taker) {
        case 'a':
            result.a += amount;
            break;
        case 'b':
            result.b += amount;
            break;
        case 'c':
            result.c += amount;
            break;

        default:
            break;
    }
    return result;
}

int getNum(state state1) {
    return state1.a * 10000 + state1.b * 100 + state1.c;
}

queue<state> queue1;
set<int> result;

bool bfs(state state1) {
    queue1.emplace(state1);
    while (!queue1.empty()) {
        state state1 = queue1.front();
        visit[getNum(state1)] = 1;
        if (state1.a == 0) {
            result.insert(state1.c);
        }

        queue1.pop();
        vector<char> canGive;
        vector<char> canTake;
        if (state1.a != 0) canGive.push_back('a');
        if (state1.b != 0) canGive.push_back('b');
        if (state1.c != 0) canGive.push_back('c');

        if (state1.a != a_max) canTake.push_back('a');
        if (state1.b != b_max) canTake.push_back('b');
        if (state1.c != c_max) canTake.push_back('c');

        for (char giver:canGive) {
            for (char taker : canTake) {
                if (giver == taker) continue;
                int remain = getRemain(state1, taker);
                int shouldGive = getShouldGive(state1, giver);
                int howMuch;
                if (shouldGive < remain) {
                    howMuch = shouldGive;
                } else {
                    howMuch = remain;
                }
                state new_state = give(state1, giver, taker, howMuch);
                if (visit.count(getNum(new_state)) == 0) {
                    queue1.emplace(new_state);
                }
            }
        }
        canGive.clear();
        canTake.clear();

    }
    return false;
}

int main() {
    int a, b, c;
    cin >> a_max >> b_max >> c_max;
    bfs(state(0, 0, c_max));
    for (int result1 : result) {
        cout << result1 << ' ';
    }

}

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

문제

문제

출처

ICPC

2251 물통 반례 있으신분 계신가요..?

ojh4110 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말