COLLECT - VOI05 Bộ sưu tập
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <queue>
#include <map>
using namespace std;
int z, s, m, z0, s0, m0;
queue<int> qx, qy, qz;
int change[1010][6];
map<pair<int,pair<int,int> >, int> ma;
int n, k;
vector< pair<int, pair<int,int> > > ds;
int main() {
scanf("%d", &k);
scanf("%d%d%d%d%d%d", &z, &s, &m, &z0, &s0, &m0);
while(scanf("%d%d%d%d%d%d", change[n], change[n]+1, change[n]+2, change[n]+3, change[n]+4, change[n]+5)!=EOF) ++n;
qx.push(z);
qy.push(s);
qz.push(m);
ma[make_pair(z,make_pair(s,m))] = 0;
while(!qx.empty()) {
z = qx.front(); qx.pop();
s = qy.front(); qy.pop();
m = qz.front(); qz.pop();
int step = ma[make_pair(z,make_pair(s,m))];
if(z>=z0 && s>=s0 && m>=m0) {
ds.push_back(make_pair(z, make_pair(s,m)));
continue;
}
if(step>=k) continue;
for(int i=0;i<n;++i) {
if(z>=change[i][0] && s>=change[i][1] && m>=change[i][2]) {
int nz = z - change[i][0] + change[i][3];
int ns = s - change[i][1] + change[i][4];
int nm = m - change[i][2] + change[i][5];
if(nz>4 || ns>4 || nm>4) continue;
pair<int, pair<int,int> > state = make_pair(nz, make_pair(ns, nm));
if(!ma.count(state)) {
ma[state] = step + 1;
qx.push(nz);
qy.push(ns);
qz.push(nm);
}
}
}
}
if(ds.size()==0) cout << -1 << endl;
else {
cout << ds.size() << endl;
sort( ds.begin(), ds.end());
for(int i=0;i<ds.size();++i) {
cout << ds[i].first << " " << ds[i].second.first << " " << ds[i].second.second << " " << ma[ds[i]] << endl;
}
}
//system("pause");
return 0;
}