SPOJ.COM - Thuật toán bài CHESSCBG - Bàn cờ thế

#include<iostream>
using namespace std;

const int MAX_INT = 1 << 30;
const int MAX = 100000;

// Mảng lưu giá trị lũy thừa của 2 tại các vị trí.
// Ví dụ tại vị trí 0 - tương ứng với 2^15 = 32768
const int Po2[16] = {32768, 16384, 8192, 4096, 2048, 1024,
                     512, 256, 128, 64, 32, 16, 8, 4, 2, 1};

int MinStep;    // Số bước nhỏ nhất để chuyển từ Map nguồn thành Map đích.
int Init[2];    // Lưu trạng thái của Map đầu và cuối dưới dạng số.
int Mark[MAX];  // Đánh dấu với mỗi trạng thái thì số bước nhỏ nhất là bao nhiêu
int State[16];  // Trạng thái của ma trận.

// Biểu diễn hàng đợi vòng
int queue[MAX];
int fr, re, leng;

void Enqueue(int stt)
{
	queue[re] = stt;
	re = (re + 1) % MAX;
	leng++;
}

int Dequeue()
{
	int stt = queue[fr];
	fr = (fr + 1) % MAX;
	leng--;
	return stt;
}

/*
* @PARAM: value : số đầu vào cần chuyển đổi thành ma trận trạng thái
*/
void ConvertInt2Matrix(int value)
{
	for(int i = 0; i < 16; i++)
	{
		int _c = i % 4;
		int _r = (i - _c) / 4;

		// Kiểm tra xem chữ số nào mà bằng 1 thì cho giá trị ma trận = 1
		// ngược lại là 0
		if((1 << i) & value) State[15 - i] = 1;
		else State[15 - i] = 0;
	}
}

int drow[4] = {-1,0,1, 0};
int dcol[4] = { 0,1,0,-1};

void BFS(int init)
{
	fr = re = leng = 0;
	for(int i = 0; i < MAX; i++)
		Mark[i] = MAX_INT;

	// Trạng thái đầu tiên
	Mark[init] = 0;
	Enqueue(init);

	while(leng > 0)
	{
		int begin = Dequeue();

		// Chuyển giá trị state vào ma trận.
		ConvertInt2Matrix(begin);

		// Duyệt các trạng thái.
		for(int i = 0; i < 16; i++)
			if(State[i] == 1)
			{
				// Tính tọa độ tương ứng trên ma trận
				int _c = i % 4;
				int _r = (i - _c) / 4;

				// Kiểm tra 4 hướng xem với số 1 di chuyển 4 hướng
				// thì trạng thái tiếp theo là gì.
				for(int j = 0; j < 4; j++)
				{
					int r = _r + drow[j];
					int c = _c + dcol[j];

					if(r >= 0 && r < 4 && c >= 0 && c < 4 && State[r*4+c] == 0)
					{
						// Tính giá trị của số mới
						// với việc số 1 ở vị trí ban đầu (_r*4 + _c) chuyển thành 0
						// số 0 ở vị trí (r*4 + c) chuyển thành 1
						int value = begin + Po2[r*4+c] - Po2[_r*4+_c];

						if((Mark[value] == MAX_INT || Mark[value] > Mark[begin] + 1))
						{
							Mark[value] = Mark[begin] + 1;
							Enqueue(value);
						}
					}
				}
			}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);

	// Nhập đầu vào.
	// Convert trạng thái Map thành số nguyên,
	// vì tại mỗi ô của Map chỉ có 2 trạng thái 0, 1.
	for(int k = 0; k < 2; k++)
	{
		Init[k] = 0;
		for(int i = 0; i < 4; i++)
		{
			char temp[5];
			cin >> temp;
			for(int j = 0; j < 4; j++)
				Init[k] = Init[k] * 2 + (temp[j] - '0');
		}
	}

	// BFS từ trạng thái ban đầu cho đến khi gặp trạng thái đích
	BFS(Init[0]);

	// In kết quả
	cout << Mark[Init[1]] << endl;

	return 0;
}