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