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;
}

Download