Cod sursa(job #3247838)

Utilizator alexandrabeldikBeldica Alexandra alexandrabeldik Data 9 octombrie 2024 15:24:12
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <queue>

using namespace std;

const int Nmax = 1005;

int A, B, C;

bool viz[Nmax][Nmax];

struct Stare {
    int x, y;
};

queue<Stare> Q;

struct Move {
    Stare prev;
    char move1, move2;
};

Move moves[Nmax][Nmax];
// moves[x][y] = ultima miscare facuta ca sa ajung in starea (x, y)

Move solution[Nmax * Nmax];
int len = 0;

void reconst(Stare st) {
    if(st.x == 0 && st.y == 0) {
        return;
    }
    reconst(moves[st.x][st.y].prev);
    solution[++len] = moves[st.x][st.y];
}

int main() {
    ifstream fin("vase.in");
    ofstream fout("vase.out");
    Stare final;
    fin >> A >> B >> C;
    viz[0][0] = true;
    Q.push({0, 0});
    while(!Q.empty()) {
        Stare stare = Q.front();
        Q.pop();

        if(stare.x == C || stare.y == C) {
            final = stare;
            break;
        }

        // umplem primul vas:
        if(!viz[A][stare.y]) {
            viz[A][stare.y] = true;
            moves[A][stare.y] = {stare, 'R', 'A'};
            Q.push({A, stare.y});
        }

        // umplem al 2lea vas:
        if(!viz[stare.x][B]) {
            viz[stare.x][B] = true;
            moves[stare.x][B] = {stare, 'R', 'B'};
            Q.push({stare.x, B});
        }

        // golim primul vas:
        if(!viz[0][stare.y]) {
            viz[0][stare.y] = true;
            moves[0][stare.y] = {stare, 'A', 'C'};
            Q.push({0, stare.y});
        }

        // golim al 2lea vas:
        if(!viz[stare.x][0]) {
            viz[stare.x][0] = true;
            moves[stare.x][0] = {stare, 'B', 'C'};
            Q.push({stare.x, 0});
        }

        // primul -> al 2lea:
        int cant = min(stare.x, B - stare.y);
        if(!viz[stare.x - cant][stare.y + cant]) {
            viz[stare.x - cant][stare.y + cant] = true;
            moves[stare.x - cant][stare.y + cant] = {stare, 'A', 'B'};
            Q.push({stare.x - cant, stare.y + cant});
        }

        // al 2lea -> primul:
        cant = min(stare.y, A - stare.x);
        if(!viz[stare.x + cant][stare.y - cant]) {
            viz[stare.x + cant][stare.y - cant] = true;
            moves[stare.x + cant][stare.y - cant] = {stare, 'B', 'A'};
            Q.push({stare.x + cant, stare.y - cant});
        }
    }

    reconst(final);

    fout << len << "\n";
    for(int i = 1; i <= len; i++) {
        fout << solution[i].move1 << " " << solution[i].move2 << "\n";
    }

}