AOJ0503
問題:Cup
kyuridenamida「がんばって幅優先です」
といわれてがんばった。
きたないけどゆるしてね
#include<iostream> #include<vector> #include<queue> #include<map> using namespace std; struct Node { int a,b,c; Node():a(0),b(0),c(0){} bool operator < ( const Node& other ) const { if( a != other.a )return a < other.a; if( b != other.b )return b < other.b; return c < other.c; } bool ok() const { return !a && !b || !b && !c ; } }; int table[20]; int main() { for( int i=0; i<20; ++i) { table[i] = 1<<i; } int n,m; while( cin >> n >> m , n|m ) { map< Node , int > step; Node input; int a,b,c; cin >> a; for( int i=0; i<a; ++i ) { int k; cin >> k; input.a |= 1<<(k-1); } cin >> b; for( int i=0; i<b; ++i ) { int k; cin >> k; input.b |= 1<<(k-1); } cin >> c; for( int i=0; i<c; ++i ) { int k; cin >> k; input.c |= 1<<(k-1); } queue< Node > q; q.push( input ); if( input.ok() ) { cout << 0 << endl; continue; } int ans=0; bool found = false; while( !found && q.size() ) { Node node; //A<->B node = q.front(); if( a|b ) { int x = node.a ^ node.b; int k; for( k=19; x<table[k]; --k ); if( node.a > node.b ) { node.a -= table[k]; node.b += table[k]; } else { node.a += table[k]; node.b -= table[k]; } if( node.ok() && step[q.front()] < m) { found = true; ans = step[q.front()] + 1; } else if( step.find(node) == step.end() && step[q.front()] < m ) { step[node] = step[q.front()] + 1; q.push( node ); } } //B<->C node = q.front(); if( b|c ) { int x = node.b ^ node.c; int k; for( k=19; x<table[k]; --k ); if( node.b > node.c ) { node.b -= table[k]; node.c += table[k]; } else { node.b += table[k]; node.c -= table[k]; } if( node.ok() ) { found = true; ans = step[q.front()] + 1; } else if( step.find(node) == step.end() && step[q.front()] < m ) { step[node] = step[q.front()] + 1; q.push( node ); } } q.pop(); } if( found ) { cout << ans << endl; } else { cout << -1 << endl; } } return 0; }