#include<bits/stdc++.h> using namespace std; map<pair<int,pair<int,int> >,bool > mp; int A,B,C; int ODP[(int)1e5+5]; queue <pair<pair<int,int>,pair<int,int> > > ko; void bfs(int a,int b, int c,int kol){ mp[{a,{b,c}}]=1; if(!ODP[a])ODP[a]=kol; if(!ODP[b])ODP[b]=kol; if(!ODP[c])ODP[c]=kol; //1 z a do b if(b+a>B and !mp[{b+a-B,{B,c}}])ko.push({{kol+1,b+a-B},{B,c}}); if(b+a<=B and !mp[{0,{b+a,c}}])ko.push({{kol+1,0},{b+a,c}}); //2 z b do a if(b+a>A and !mp[{A,{b+a-A,c}}])ko.push({{kol+1,A},{b+a-A,c}}); if(b+a<=A and !mp[{b+a,{0,c}}])ko.push({{kol+1,b+a},{0,c}}); //3 z a do c if(c+a>C and !mp[{c+a-C,{b,C}}])ko.push({{kol+1,c+a-C},{b,C}}); if(c+a<=C and !mp[{0,{b,a+c}}])ko.push({{kol+1,0},{b,a+c}}); //4 z c do a if(c+a>A and !mp[{A,{b,c+a-A}}])ko.push({{kol+1,A},{b,c+a-A}}); if(c+a<=A and !mp[{c+a,{b,0}}])ko.push({{kol+1,c+a},{b,0}}); //5 z b do c if(c+b>C and !mp[{a,{b+c-C,C}}])ko.push({{kol+1,a},{b+c-C,C}}); if(c+b<=C and !mp[{a,{0,b+c}}])ko.push({{kol+1,a},{0,b+c}}); //6 z c do b if(c+b>B and !mp[{a,{B,c+b-B}}])ko.push({{kol+1,a},{B,c+b-B}}); if(c+b<=B and !mp[{a,{b+c,0}}])ko.push({{kol+1,a},{b+c,0}}); } int main(){ ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); int a,b,c;cin>>A>>B>>C>>a>>b>>c; ko.push({{1,a},{b,c}}); while(!ko.empty()){ pair<pair<int,int>,pair<int,int> > p=ko.front(); pair<int,int> k=p.first;pair<int,int> ai=p.second; int ki=k.first;int ais=k.second;int heses=ai.first;int ces=ai.second; //cout<<ais<<" "<<heses<<" "<<ces<<" "<<ki<<"\n"; bfs(ais,heses,ces,ki); ko.pop(); } for(int i=0;i<=C;i++)cout<<ODP[i]-1<<" "; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include<bits/stdc++.h> using namespace std; map<pair<int,pair<int,int> >,bool > mp; int A,B,C; int ODP[(int)1e5+5]; queue <pair<pair<int,int>,pair<int,int> > > ko; void bfs(int a,int b, int c,int kol){ mp[{a,{b,c}}]=1; if(!ODP[a])ODP[a]=kol; if(!ODP[b])ODP[b]=kol; if(!ODP[c])ODP[c]=kol; //1 z a do b if(b+a>B and !mp[{b+a-B,{B,c}}])ko.push({{kol+1,b+a-B},{B,c}}); if(b+a<=B and !mp[{0,{b+a,c}}])ko.push({{kol+1,0},{b+a,c}}); //2 z b do a if(b+a>A and !mp[{A,{b+a-A,c}}])ko.push({{kol+1,A},{b+a-A,c}}); if(b+a<=A and !mp[{b+a,{0,c}}])ko.push({{kol+1,b+a},{0,c}}); //3 z a do c if(c+a>C and !mp[{c+a-C,{b,C}}])ko.push({{kol+1,c+a-C},{b,C}}); if(c+a<=C and !mp[{0,{b,a+c}}])ko.push({{kol+1,0},{b,a+c}}); //4 z c do a if(c+a>A and !mp[{A,{b,c+a-A}}])ko.push({{kol+1,A},{b,c+a-A}}); if(c+a<=A and !mp[{c+a,{b,0}}])ko.push({{kol+1,c+a},{b,0}}); //5 z b do c if(c+b>C and !mp[{a,{b+c-C,C}}])ko.push({{kol+1,a},{b+c-C,C}}); if(c+b<=C and !mp[{a,{0,b+c}}])ko.push({{kol+1,a},{0,b+c}}); //6 z c do b if(c+b>B and !mp[{a,{B,c+b-B}}])ko.push({{kol+1,a},{B,c+b-B}}); if(c+b<=B and !mp[{a,{b+c,0}}])ko.push({{kol+1,a},{b+c,0}}); } int main(){ ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); int a,b,c;cin>>A>>B>>C>>a>>b>>c; ko.push({{1,a},{b,c}}); while(!ko.empty()){ pair<pair<int,int>,pair<int,int> > p=ko.front(); pair<int,int> k=p.first;pair<int,int> ai=p.second; int ki=k.first;int ais=k.second;int heses=ai.first;int ces=ai.second; //cout<<ais<<" "<<heses<<" "<<ces<<" "<<ki<<"\n"; bfs(ais,heses,ces,ki); ko.pop(); } for(int i=0;i<=C;i++)cout<<ODP[i]-1<<" "; return 0; } |