SPOJ.COM - Thuật toán bài QKP - Queens, Knights and Pawns

Posted on November 5th, 2016

Đề bài:

Tất cả bạn có thể đã quen thuộc với bài toán nổi tiếng 8 con hậu - bài toán yêu cầu bạn đặt 8 con hậu trên một bàn cờ sao cho không có 2 con nào có thể tấn công được nhau. Ở bài toán này, bạn được cho vị trí của quân hậu (Q), quân mã (K) và quân tốt (P) và yêu cầu bạn tìm ra xem có bao nhiêu ô trống mà không bị tấn công bởi con con mã hoặc con hậu hoặc cả hai. Chúng ta sẽ gọi những ô này là ô an toàn (safe). Ở đây, quân tốt được xem như là các vật cản mà không có khả năng tấn công. Bảng sau có 6 ô an toàn (là các ô tô đậm hơn)

spoj-com-thuat-toan-bai-qkp-queens-knights-and-pawns-pic-thuattoan-phamvanlam-com

Nhắc lại rằng, con mã chỉ có thể di chuyển tới bất kì một ô rảnh nào mà nó ở góc đối diện của hình chữ nhât kích thước 2x3. Con hậu có thể di chuyển theo 8 hướng. Chú ý rằng, con hậu có thể bị chặn bởi các con khác, trong khi con mã thì sẽ không bị chặn bởi con khác.

Đầu vào

Bao gồm nhiều test case. Mỗi test case sẽ bao gồm 4 dòng. Dòng đầu tiên bao gồm 2 số nguyên n, m - biểu diễn kích thước của bàn cờ, tương ứng với số hàng và số cột, n, m không quá 1000. 3 dòng tiếp theo sẽ có dạng như sau:

k r1 c1 r2 c2 · · · rk ck

xác định số lượng và vị trí của các con hậu, mã, và tốt. Chỉ số hàng, cột sẽ bắt đầu từ 1. Mỗi loại sẽ có tối đa 100 con. Giá trị n=m=0 xác định kết thúc đầu vào.

Đầu ra

Mỗi test case sẽ in ra dạng : Board b has s safe squares. Trong đó, b là chỉ số của bàn cờ, bắt đầu từ 1 và s là số ô an toàn tương ứng.

Ví dụ

Đầu vào:

4 4
2 1 4 2 4
1 1 2
1 2 3
2 3
1 1 2
1 1 1
0
1000 1000
1 3 3
0
0
0 0

Đầu ra:


Board 1 has 6 safe squares.
Board 2 has 0 safe squares.
Board 3 has 996998 safe squares.

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

Phân tích

Ở đây mình sẽ sử dụng thuật toán tham lam Greedy để giải bài toán.

  • Với mỗi con mã, mình sẽ duyệt 8 hướng và đếm vị trí mỗi con mã có thể ăn. Sau khi tính xong thì mình sẽ đánh dấu rằng vị trí đó đã được ăn để không bị trùng lặp cho lần sau.

  • Sau khi duyệt xong hết con mã sẽ đến con hậu.

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 Q         = 0;
const int K         = 1;
const int P         = 2;
const int Safe      = 3;
const int Unsafe    = 4;

int Board[1000][1000];	// Lưu bàn cờ
int ROW, COL;			// Số hàng ,cột

// Đường đi con mã
int K_row[8] = {-1,-2, 1, 2,-2,-1, 2, 1};
int K_col[8] = { 2, 1, 2, 1,-1,-2,-1,-2};

/*
* Tính số ô con mã có thể ăn
* @PARAM: row, hàng của con mã đang xét
* @PARAM: col, cột của con mã đang xét
* RETURN: số vị trí con mã có thể ăn
*/
int checkK(int row, int col)
{
	int count = 0;
	// Kiểm tra 8 hướng của con mã
	for(int i = 0; i < 8; i++)
	{
		int r = row + K_row[i];
		int c = col + K_col[i];
		if(r <= ROW && r >= 0 && c <= COL && c >= 0)
		{
			// Nếu ô nào đang ở vị trí an toàn
			// thì tức là con mã có thể ăn
			// cho ô đó thành Unsafe để tránh lặp và tăng biến đếm
			if(Board[r][c] == Safe)
			{
				Board[r][c] = Unsafe;
				count++;
			}
		}
	}
	return count;
}

// Đường đi con hậu
int Q_row[8] = { 0, 0, 1, 1, 1,-1,-1,-1};
int Q_col[8] = { 1,-1,-1, 0, 1,-1, 0, 1};
int Sum = 0;

/*
* Duyệt mỗi con hậu tại vị trí row, col theo từng hướng
* Sử dụng đệ quy
*/
void checkQ(int row, int col, int direct)
{
	int r = row + Q_row[direct];
	int c = col + Q_col[direct];

	if(r <= ROW && r >= 0 && c <= COL && c >= 0)
	{
		// Ô nào đang an toàn thì sẽ bị ăn
		// Cho thành Unsafe
		if(Board[r][c] == Safe)
		{
			Board[r][c] = Unsafe;
			Sum--;
			checkQ(r, c, direct);
		}
		else if(Board[r][c] == Unsafe)
		{
			// Trường hợp này là đã tính trước đó.
			checkQ(r,c,direct);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);
	int tc = 0;
	while(true)
	{
		cin >> ROW >> COL;
		if(ROW == 0 && COL == 0) break;
		tc ++;
		Sum = ROW * COL;
		ROW--;
		COL--;

		// Ban đầu gán các ô là ô an toàn
		for(int r = 0; r <= ROW; r++)
			for(int c = 0; c <= COL; c++)
				Board[r][c] = Safe;

		int r, c;
		int row[2][100], col[2][100];	// Lưu thông tin con hậu, con mã
		int num[3];						// Số lượng con hậu, con mã, con tốt

		// Tiếp tục nhập đầu vào
		for(int i = 0; i < 3; i++)
		{
			cin >> num[i];
			for(int j = 0; j < num[i]; j++)
			{
				cin >> r >> c;
				Board[r-1][c-1] = i;
				if(i != 2)
				{
					row[i][j] = r - 1;
					col[i][j] = c - 1;
				}
			}
		}

		// Tính tổng các ô rảnh mà chưa có con nào đang đứng
		Sum -= num[Q] + num[K] + num[P];

		// Duyệt các con mã
		for(int j = 0; j < num[K]; j++)
			Sum -= checkK(row[K][j],col[K][j]);

		// Duyệt các con hậu
		for(int j = 0; j < num[Q]; j++)
			for(int i = 0; i < 8; i++)
				checkQ(row[Q][j], col[Q][j], i);

		cout <<"Board "<< tc <<" has " << Sum << " safe squares."<< 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é: