COLLECT - VOI05 Bộ sưu tập
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
struct state {
int z, s, m, k;
state() {}
state(int z, int s, int m, int k): z(z), s(s), m(m), k(k) {}
state(int z, int s, int m): z(z), s(s), m(m), k(0) {}
bool operator < (const state &a) const {
return z != a.z ? z < a.z : s != a.s ? s < a.s : m != a.m ? m < a.m : k != a.k ? k < a.k : 0;
}
};
bool vst[5][5][5];
vector<pair<state, state> > conv;
int z, s, m, z0, s0, m0, k;
void enter() {
scanf("%d%d%d%d%d%d%d", &k, &z, &s, &m, &z0, &s0, &m0);
for(int z1,s1,m1,z2,s2,m2; scanf("%d%d%d%d%d%d",&z1,&s1,&m1,&z2,&s2,&m2) == 6; )
conv.push_back(make_pair(state(z1,s1,m1), state(z2,s2,m2)));
}
void solve() {
queue<state> q; q.push(state(z, s, m)); vst[z][s][m] = 1;
vector<state> res;
while(!q.empty()) {
state u = q.front(); q.pop();
//printf("* %d %d %d %d\n", u.z, u.s, u.m, u.k);
if(u.z >= z0 && u.s >= s0 && u.m >= m0) res.push_back(u);
else TR(conv, it) {
if(u.z >= it->first.z && u.s >= it->first.s && u.m >= it->first.m && u.k + 1 <= k) {
int z = u.z - it->first.z + it->second.z;
int s = u.s - it->first.s + it->second.s;
int m = u.m - it->first.m + it->second.m;
if(z <= 4 && s <= 4 && m <= 4 && vst[z][s][m] == 0)
vst[z][s][m] = 1, q.push(state(z, s, m, u.k+1));
}
}
}
if(res.empty()) printf("-1\n");
else {
printf("%u\n", res.size());
sort(res.begin(), res.end());
TR(res, u) printf("%d %d %d %d\n", u->z, u->s, u->m, u->k);
}
}
int main() {
enter();
solve();
return 0;
}