Pagini recente » Cod sursa (job #3140245) | Cod sursa (job #3243181) | Cod sursa (job #2948808) | Cod sursa (job #1793442) | Cod sursa (job #3247838)
#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";
}
}