Artifact e714e7afac0b764b2504a44dfbe3c872e11cb9c0
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
class PiecesMover
{
public:
static bool is_connected(int cur)
{
int py[5], px[5], pn=0;
for(int j=0; j<25; ++j)
if( cur & (1<<j) )
py[pn]=j/5, px[pn]=j%5, pn++;
int uf[5] = {0,1,2,3,4}, conn = pn;
for(int i=0; i<pn; ++i)
for(int j=i+1; j<pn; ++j)
if( px[i]==px[j] && abs(py[i]-py[j])==1
|| py[i]==py[j] && abs(px[i]-px[j])==1 ) {
int a=i; while(uf[a]!=a) a=uf[a];
int b=j; while(uf[b]!=b) b=uf[b];
if(a!=b) { uf[a]=b, --conn; }
}
return conn==1;
}
int getMinimumMoves(vector <string> board)
{
int start = 0;
for(int i=0; i<25; ++i)
if( board[i/5][i%5]=='*' )
start |= (1<<i);
vector<bool> visited(1<<25); visited[start] = false;
vector<int> Q(1, start);
int step = 0;
for(;; ++step)
{
vector<int> Q2;
for(int i=0; i!=Q.size(); ++i)
{
int cur = Q[i];
if( is_connected(cur) )
return step;
// next
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
for(int j=0; j<25; ++j)
if( cur & (1<<j) )
for(int k=0; k<4; ++k)
{
int jy=j/5+dy[k], jx=j%5+dx[k];
if(0<=jy && jy<5 && 0<=jx && jx<5) {
int next = 1 << (jy*5+jx);
if( !(cur&next) ) {
next = cur&~(1<<j)|next;
if( !visited[next] ) {
visited[next]=true;
Q2.push_back(next);
}
}
}
}
}
Q.swap(Q2);
}
return -1;
}
};
int main()
{
vector<string> x;
x.push_back(".....");
x.push_back("..**.");
x.push_back(".....");
x.push_back("...*.");
x.push_back(".....");
cout << PiecesMover().getMinimumMoves(x) << endl;;
}