The Solver for Gnome Game, Lights Off

lightoff.cpp

#include <iostream>
#include <cstring>
#include <algorithm>

#define		N	5
#define		NN	25
#define		limit	30
#define		maxqueue 10000000

using namespace std;

int bit[NN];

struct scheme
{
	bool M[N][N];
	bool click[N][N];
};


struct queue_type
{
	scheme status;
	int step;
	int pre;
	int x, y;
};

bool flag[1 << (NN + 1)];


scheme start;

scheme final;

queue_type queue[maxqueue];

void change(scheme &P, int x, int y)
{
	P.M[x][y] = !P.M[x][y];
	if (x > 0) P.M[x - 1][y] = !P.M[x - 1][y];
	if (x < N - 1) P.M[x + 1][y] = !P.M[x + 1][y];
	if (y > 0) P.M[x][y - 1] = !P.M[x][y - 1];
	if (y < N - 1) P.M[x][y + 1] = !P.M[x][y + 1];
}


int hash(const scheme &X)
{
	int ret = 0;	
	for (int i = 0; i < N; ++ i)
		for (int j = 0; j < N; ++ j)
			if (X.M[i][j])
				ret += bit[i * N + j];
	return ret;
}


void print_path(int k)
{
	cout << queue[k].step << endl;
	int cur = 0;	
	while (k != -1)
	{
		/*
		++ cur;
		cout << cur << ":===========================" << endl;
		*/
		cout << queue[k].x + 1 << " " << queue[k].y + 1 << endl;
		/*
		for (int i = 0; i < N; ++ i)
		{
			for (int j = 0; j < N; ++ j)
				if (queue[k].status.M[i][j])
					cout << '*';
				else
					cout << 'x';
			cout << endl;
		}
		*/
		k = queue[k].pre;
	}
}

void bfs(const scheme &S)
{
	queue[0].status = S;
	queue[0].step = 0;
	queue[0].pre = -1;
	queue[0].x = queue[0].y = -1;
	memset(queue[0].status.click, true, sizeof(queue[0].status.click));

	memset(flag, true, sizeof(flag));

	flag[hash(S)] = false;
	
	int head, tail;
	head = tail = 0;
	scheme temp;
	while (head <= tail)
	{
		temp = queue[head].status;

		for (int i = 0; i < N; ++ i)
			for (int j = 0; j < N; ++ j)
			if (temp.click[i][j])
			{
				change(temp, i, j);
				temp.click[i][j] = false;
				int check = hash(temp);
				if (flag[check])
				{
					flag[check] = false;
					++ tail;
					queue[tail].status = temp;
					queue[tail].pre = head;
					queue[tail].step = queue[head].step + 1;
					queue[tail].x = i;
					queue[tail].y = j;
					if (check == 0)
					{
						print_path(tail);
						cout << tail << endl;
						return;
					}
				}
				change(temp, i, j);
				temp.click[i][j] = true;
			}

		++ head;
	}
}


void init()
{
	bit[0] = 1;
	for (int i = 1; i < limit; ++ i)
		bit[i] = bit[i - 1] << 1;

	string s;
	for (int i = 0; i < N; ++ i)
	{
		cin >> s;
		for (int j = 0; j < N; ++ j)
			start.M[i][j] = ('*' == s[j]);
	}
	memset(final.M, 0, sizeof(final.M));
/*
	for (int i = 0; i < N; ++ i)
	{
		for (int j = 0; j < N; ++ j)
			cout << start.M[i][j];
		cout << endl;
	}
*/
}

int main()
{
	init();
	bfs(start);
	return 0;
}

lightoff_v2.cpp

#include <iostream>
#include <cstring>
#include <algorithm>

#define		N	5
#define		NN	25
#define		limit	30
#define		maxqueue 1 << (NN + 1)

using namespace std;

int bit[NN];

struct queue_type
{
	int status;
	int step;
	int pre;
	int cache;
	int x, y;
};

bool flag[maxqueue];


int start, final;

int X[NN];

queue_type queue[maxqueue];

void print_path(int k)
{
	cout << queue[k].step << endl;
	while (k != 0)
	{
		cout << queue[k].x + 1 << " " << queue[k].y + 1 << endl;
		k = queue[k].pre;
	}
}

void bfs(const int S)
{
	queue[0].status = S;
	queue[0].step = 0;
	queue[0].pre = -1;
	queue[0].x = queue[0].y = -1;
	queue[0].cache = 0;

	memset(flag, true, sizeof(flag));

	flag[S] = false;
	
	int head, tail;
	head = tail = 0;
	int temp;
	while (head <= tail)
	{
		temp = queue[head].status;

		for (int i = queue[head].cache; i < N * N; ++ i)
		{
				temp = temp ^ X[i];
				if (flag[temp])
				{
					flag[temp] = false;
					++ tail;
					queue[tail].status = temp;
					queue[tail].pre = head;
					queue[tail].step = queue[head].step + 1;
					queue[tail].cache = i + 1;
					queue[tail].x = i / N;
					queue[tail].y = i % N;
					if (temp == final)
					{
						print_path(tail);
						cout << tail << endl;
						return;
					}
				}
				temp = temp ^ X[i];
			}

		++ head;
	}
}

void init()
{
	bit[0] = 1;
	for (int i = 1; i < limit; ++ i)
		bit[i] = bit[i - 1] << 1;

	string s;

	start = final = 0;

	for (int i = 0; i < N; ++ i)
	{
		cin >> s;
		for (int j = 0; j < N; ++ j)
			if ('*' == s[j])
				start += bit[i * N + j];
	}


	X[0] = 1 + (1 << 1) + (1 << 5);
	X[1] = 1 + (1 << 1) + (1 << 2) + (1 << 6);
	X[2] = (1 << 1) + (1 << 2) + (1 << 3) + (1 << 7);
	X[3] = (1 << 4) + (1 << 2) + (1 << 3) + (1 << 8);
	X[4] = (1 << 4) + (1 << 3) + (1 << 9);

	X[5] = 1 + (1 << 5) + (1 << 6) + (1 << 10);
	X[6] = (1 << 5) + (1 << 6) + (1 << 7) + (1 << 1) + (1 << 11);
	X[7] = (1 << 8) + (1 << 6) + (1 << 7) + (1 << 2) + (1 << 12);
	X[8] = (1 << 8) + (1 << 9) + (1 << 7) + (1 << 3) + (1 << 13);
	X[9] = (1 << 8) + (1 << 9) + (1 << 4) + (1 << 14);

	X[10] = (1 << 5) + (1 << 10) + (1 << 11) + (1 << 15);
	X[11] = (1 << 10) + (1 << 11) + (1 << 12) + (1 << 6) + (1 << 16);
	X[12] = (1 << 13) + (1 << 11) + (1 << 12) + (1 << 7) + (1 << 17);
	X[13] = (1 << 13) + (1 << 14) + (1 << 12) + (1 << 8) + (1 << 18);
	X[14] = (1 << 13) + (1 << 14) + (1 << 9) + (1 << 19);

	X[15] = (1 << 10) + (1 << 15) + (1 << 16) + (1 << 20);
	X[16] = (1 << 15) + (1 << 16) + (1 << 17) + (1 << 16) + (1 << 21);
	X[17] = (1 << 18) + (1 << 16) + (1 << 17) + (1 << 17) + (1 << 22);
	X[18] = (1 << 18) + (1 << 19) + (1 << 17) + (1 << 18) + (1 << 23);
	X[19] = (1 << 18) + (1 << 19) + (1 << 14) + (1 << 24);

	X[20] = (1 << 15) + (1 << 20) + (1 << 21);
	X[21] = (1 << 20) + (1 << 21) + (1 << 22) + (1 << 16);
	X[22] = (1 << 23) + (1 << 21) + (1 << 22) + (1 << 17);
	X[23] = (1 << 23) + (1 << 24) + (1 << 22) + (1 << 18);
	X[24] = (1 << 23) + (1 << 24) + (1 << 19);
}

int main()
{
	init();
	bfs(start);
	return 0;
}

sample.in

00000
00000
00*00
00000
00000