Artifact e714e7afac0b764b2504a44dfbe3c872e11cb9c0

• File SRM/425/1B.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#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;;
}