floodit.cpp

Floodit Solver, using STL.

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#define x first
#define y second

using namespace std;

struct node{
	int G[14][14], pastc;
	vector<int> Path;
	int step, heu;
	node(){memset(G, 0, sizeof(G)), step=0, heu=195, pastc=-1;Path.clear();}
	node(int **p, int tstep, int tpastc, vector<int> tPath){
		for (int i = 0 ; i < 14; ++i)
			for (int j = 0 ; j < 14; ++j)
				G[i][j] = p[i][j];
		step=tstep;
		pastc=tpastc;
		Path = tPath;
	}
	bool operator<(const node &S)const{
		return step+heu < S.step+S.heu;
	}
	bool operator>(const node &S)const{
		return step+heu > S.step+S.heu;
	}
};

node Glo;
vector<pair<int, int> > E[6];
vector<pair<int, int> > R;
char conv[6] = {'p','b','y','g','d','r'};

struct M{
	int G[14][14];
	M(){memset(G, 0, sizeof(G));}
	M(node P){memcpy(G, P.G, sizeof(G));}
	void print(){
		for (int i = 0 ; i < 14; puts(""), ++i)
			for (int j = 0 ; j < 14; ++j)
				printf("%c", conv[G[i][j]]);
		puts("");
	}
	bool operator<(const M &S)const{
		for (int i = 0 ; i <14; ++i)
			for (int j = 0 ; j < 14; ++j)
				if (G[i][j] < S.G[i][j]) return 1;
		return 0;
	}
};

bool v[14][14];

int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};

void reachable(int x, int y){
	v[x][y] = 1;
	for (int f = 0; f < 4; ++f){
		int i = dir[f][0], j = dir[f][1];
		if (x+i >= 0 && y+j >= 0)
			if (x+i < 14 && y+j < 14)
				if (!v[x+i][y+j])
					if (Glo.G[x+i][y+j] == Glo.G[0][0]){
						R.push_back(make_pair(x+i, y+j));
						reachable(x+i, y+j);
					}
					else{
						v[x+i][y+j] = 1;
						E[Glo.G[x+i][y+j]].push_back(make_pair(x+i, y+j));
					}
	}
}


void print(){
	for (int i = 0 ; i < 14; puts(""), ++i)
		for (int j = 0 ; j < 14; ++j)
			printf("%c", conv[Glo.G[i][j]]);
	puts("");
}


void ffill(int x, int y){
	v[x][y] = 1;
	for (int d = 0 ; d < 4; ++d){
		int i = dir[d][0], j = dir[d][1];
		if (x+i<0 || y+j < 0 || x+i>13 || y+j>13) continue;
		if (!v[x+i][y+j] && Glo.G[x+i][y+j] == Glo.G[x][y])
			ffill(x+i, y+j);
	}
}

int cnt, col[6];

int GetHeu(){
	int cluster=0;
	memset(v, 0, sizeof(v));
	memset(col, 0, sizeof(col));
	for (int i = 0 ; i < 14; ++i)
		for (int j = 0 ; j < 14; ++j)
			if (!v[i][j]){
				if (i || j) col[Glo.G[i][j]] = 1;
				cluster++;
				ffill(i, j);
			}
	return cluster;
}

int main(){
	node S;
	for (int i = 0 ; i < 14 ; ++i)
		for (int j = 0 ; j < 14; ++j)
			scanf("%d", &S.G[i][j]);
	S.step = 0;
	priority_queue<node, vector<node>, greater<node> > Q;
	Q.push(S);
	map<M, int> V;
	V[M(S)] = 0;
	int ans = 999;
	while (!Q.empty()){
		node T = Q.top();
		Q.pop();
		Glo = T;
		if (T.step > V[M(T)]) continue;
		if (T.step > ans) continue;
		//printf("\n******************%c (%d) (%d)*****************\n", conv[Glo.pastc], Glo.step, Glo.heu);
		//print();
		R.clear();
		memset(v, 0, sizeof(v));
		for (int i = 0 ; i < 6; ++i) E[i].clear();
		reachable(0, 0);
		if (T.G[0][0] == T.G[13][13]){
			if (R.size() == 195 && ans > T.step){
				printf("%d\n", T.step);
				for (int i = 0 ; i < T.Path.size(); ++i) printf("%c ", conv[T.Path[i]]);
				puts("");
				Glo = T;
				//print();
				ans = T.step;
				//break;
				continue;
			}
		}
		M B = M(T);
		//B.print();
		for (int i = 0 ; i < 6; ++i){
			if (i == T.G[0][0]) continue;
			if (!E[i].size()) continue;
			node X = T;
			X.G[0][0] = i;
			for (int j = 0 ; j < E[i].size(); ++j) X.G[E[i][j].x][E[i][j].y] = i;
			for (int j = 0 ; j < R.size(); ++j) X.G[R[j].x][R[j].y] = i;
			B = M(X);
			X.step++;
			Glo = X;
			//cnt = 0;
			//X.heu = GetHeu()-1;//195 - R.size() - E[i].size();
			//for (int j = 0 ; j < 6; ++j) cnt += col[j];
			X.heu = 195 - R.size() - E[i].size();
			//printf("Change to color %c\n", conv[i]);
			//B.print();
			X.pastc = i;
			X.Path.push_back(i);
			//if (X.step > ans) continue;
			if (X.step >= ans) continue;
			//if (X.step <=25)
				if (V.find(B) == V.end()){
					V[B] = X.step;
					Q.push(X);
				}else
				if (V[B] > X.step){
					V[B] = X.step;
					Q.push(X);
				}
		}
	}
	/*
	memcpy(Glo.G, S.G, sizeof(S.G));	
	R.clear();
	reachable(0, 0);
	R.push_back(make_pair(0, 0));
	print();

	for (int i = 0 ; i < Glo.Path.size(); ++i){
		R.clear();
		memset(v, 0, sizeof(v));
		reachable(0, 0);
		printf("****************%d (%d)***************\n", i+1, R.size());
		Glo.G[0][0] = Glo.Path[i];
		for (int j = 0 ; j < R.size(); ++j) Glo.G[R[j].x][R[j].y] = Glo.Path[i];
		print();
	}*/
	return 0;
}