Artifact f7ec079893dd31a3da8c37568534fd7764e27826
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class PiecesMover { public:
typedef vector< pair<int,int> > state;
int getMinimumMoves(vector <string> board)
{
set<state> V;
vector<state> Q(1, to_state(board));
V.insert( Q.front() );
for(int step=0; !Q.empty(); ++step)
{
vector<state> Q_next;
for(int i=0; i<Q.size(); ++i)
{
const state& b = Q[i];
if( is_connected(b) )
return step;
const vector<state>& next = next_states(b);
for(int j=0; j<next.size(); ++j)
if( V.insert(next[j]).second )
Q_next.push_back(next[j]);
}
Q.swap(Q_next);
}
assert(false);
}
state to_state( const vector<string>& b )
{
state s;
for(int y=0; y<5; ++y)
for(int x=0; x<5; ++x)
if( b[y][x] == '*' )
s.push_back( make_pair(y,x) );
sort( s.begin(), s.end() );
return s;
}
bool is_connected( const state& s )
{
int N = s.size();
vector< vector<int> > G(N, vector<int>(N));
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
if( i == j )
G[i][j] = 0;
else
G[i][j] = (abs(s[i].first-s[j].first)+abs(s[i].second-s[j].second) == 1 ? 1 : 100);
for(int k=0; k<N; ++k)
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
if( G[i][j] > N )
return false;
return true;
}
vector<state> next_states( const state& s )
{
vector<state> result;
for(int i=0; i<s.size(); ++i)
for(int d=0; d<4; ++d)
{
set< pair<int,int> > x;
for(int k=0; k<s.size(); ++k)
if( i != k )
x.insert( s[k] );
else
{
static const int dy[] = {-1,+1,0,0};
static const int dx[] = {0,0,-1,+1};
int ny = s[k].first+dy[d];
int nx = s[k].second+dx[d];
if( 0<=ny && ny<5 && 0<=nx && nx<5 )
x.insert( make_pair(ny, nx) );
}
if( x.size() == s.size() )
result.push_back( state(x.begin(), x.end()) );
}
return result;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, PiecesMover().getMinimumMoves(board));}
int main(){
CASE(0)
string board_[] = {".....",
"..**.",
".....",
"...*.",
"....."}
;
vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
int _ = 1;
END
CASE(1)
string board_[] = {".....",
".....",
".**..",
".*...",
"**..."}
;
vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
int _ = 0;
END
CASE(2)
string board_[] = {"*...*",
".....",
".....",
".....",
"*...*"}
;
vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
int _ = 12;
END
/*
CASE(3)
string board_[] = ;
vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
int _ = ;
END
CASE(4)
string board_[] = ;
vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
int _ = ;
END
*/
}
// END CUT HERE