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

Posted on October 20th, 2016

Đề bài:

Một bàn cờ thế là một bảng gồm 4 dòng, 4 cột. Mỗi thế cờ là một cách sắp xếp 8 quân cờ, hai quân khác nhau ở hai ô khác nhau. Bài toán đặt ra là cho hai thế cờ 1 và 2, hãy tìm một số ít nhất bước di chuyển quân để chuyển từ thế 1 sang thế 2; một bước di chuyển quân là một lần chuyển quân cờ sang ô trống kề cạnh với ô quân cờ đang đứng.

Đầu vào

Từ file văn bản gồm 8 dòng, mỗi dòng là một xâu nhị phân độ dài 4 mà số 1/0 tương ứng với vị trí có hoặc không có quân cờ. Bốn dòng đầu là thế cờ 1, bốn dòng sau là thế cờ 2.

Đầu ra

Gồm 1 dòng duy nhất là số bước chuyển quân ít nhất.

Ví dụ

Đầu vào:

1111 
0000 
1110 
0010 
1010 
0101 
1010 
0101

Đầu ra:

4 

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://vn.spoj.com/problems/CHESSCBG/

Phân tích

Ở đây, ma trận đầu vào mình sẽ lưu nó dưới dạng mảng 1 chiều. Công thức để quy đổi từ tọa độ 1 điểm trên ma trận thành tọa độ 1 điểm trên mảng và ngược lại như sau:

  • Từ điểm có tọa độ [r][c] trên ma trận thì tọa độ trên mảng là: r*N + c (trong đó N là số cột của ma trận. Ở đây N = 4). Ví dụ: một điểm ở tọa độ [1][2] (hàng 1, cột 2) thì ở trên mảng nó sẽ tương ứng với điểm 1*4 + 2 = 6 (chỉ số tính từ 0)

  • Ngược lại, từ một điểm ở trên mảng có tọa độ là t thì ở trên mảng, tọa độ của nó là: c = t % Nr = (t - c)/4. Lấy luôn ví dụ trên, với điểm trên mảng có tọa độ t = 6, thì trên mảng nó sẽ có tọa độ: c = 6 % 4 = 2 và r = (6 - 2) /4 = 1.

Như vậy, thế cờ 1 và thế cờ 2 đều có thể biểu diễn được dưới dạng mảng 1 chiều gồm 16 phần tử. Ở đây, mình sẽ sử dụng thuật toán tìm kiếm theo chiều rộng - BFS với trạng thái đầu là thế cờ 1 và trạng thái đích là thế cờ 2. Để thực hiện điều này, mình cần phải có một mảng để lưu số bước ít nhất mà từ thế cờ 1 tới thế cờ đó.

Ở đây có một điều đặc biệt đó là các phần tử của mảng chỉ bao gồm các số 0 và 1. Do đó, mình hoàn toàn có thể coi nó như là một số nhị phân. Vì vậy, mình sẽ chuyển nó thành số thập phân tương ứng để biểu diễn trạng thái đó. Với ví dụ đầu bài, thế cờ 1 là:

1111
0000 
1110 
0010

Mình chuyển nó thành mảng: 1111.0000.1110.0010. Dãy số này tương ứng với số: 61666. Đến đây là bài toán đã trở nên đơn giản hơn rồi phải không bạn.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

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

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!