SPOJ.COM - Thuật toán bài HERDING - Herding

Đề bài:

Có một lượng mèo bị lạc trong thành phố. Và bạn được giao nhiệm vụ để tìm lại được hết số mèo. Đây là cơ hội lý tưởng cho bạn để kiểm nghiệm phát minh mới nhất của bạn. Một cái bẫy mèo đảm bảo sẽ bắt được những chú mèo khi nó đi vào khu vực của thành phố.

May mắn thay, bạn được trợ giúp bởi một trong những nhà tâm lý học hàng đầu về mèo - người có khả năng kì diệu về tài tiên đoán. Cho trước một vùng hình vuông trong thành phố, và chính xác 4 hướng con mèo sẽ đi (đông, tây, nam, bắc). Trong khi những thông tin này là trong tầm tay, bạn vẫn không thể biết được những nơi mà hiện tại con mèo đang ở.

Để chứng minh tính hiệu quả về giá của phương pháp này, và dĩ nhiên là tối thiểu hoá những cái bẫy sẽ được sử dụng.

Đầu vào

Bắt đầu là một dòng gồm 2 số n và m, cách nhau bởi dấu cách,1 ≤ n, m ≤ 1000. Khu vực sẽ có kích thước nxm. n dòng tiếp theo, mỗi dòng có m kí tự, gồm 4 loại 'N', 'E', 'S', và 'W' biểu diễn hướng Bắc, Đông, Nam, Tây. Kí tự đầu tiên của dòng đầu tiên sẽ là điểm trên cùng bên trái. Hướng trên mỗi ô vuông sẽ là hướng con mèo sẽ đi, nếu con mèo ở ô đó. Đảm bảo rằng con mèo sẽ không ra khỏi thành phố.

Đầu ra

In ra số lượng bẫy tối thiểu.

Ví dụ

Đầu vào:

3 4
SWWW
SEWN
EEEN

Đầu ra:

2

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

Phân tích

• Mình nhận thấy rằng là khi con mèo đi vào thành phố, cách nó đi chính là hướng được ghi tại ô vuông nó đang đứng. Tức là hướng đã xác định trước. Do đó, để tìm được số lượng bẫy tối thiểu thì mình phải đặt bẫy làm sao mà nó ở đúng vị trí mà chắc chắn con mèo sẽ phải đi qua đó.

• Do đó, mình sẽ sử dụng thuật toán tìm kiếm theo chiều sâu DFS để xác định các đường đi đó. Mỗi đường đi mình chỉ cần đặt một cái bẫy là đủ để có thể bắt được hết số mèo.

• Xin mời bạn theo dõi code của mình phía dưới đây và cùng tìm hiểu xem thế nào nhé.

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 = 1005;
const int W   = 0;
const int N   = 1;
const int E   = 2;
const int S   = 3;

int n, m, cnt;
int Matrix[MAX][MAX], Mark[MAX][MAX];

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

bool Check(int dir, int r, int c)
{
	if(dir == W && Matrix[r][c] == E) return true;
	if(dir == E && Matrix[r][c] == W) return true;
	if(dir == S && Matrix[r][c] == N) return true;
	if(dir == N && Matrix[r][c] == S) return true;
	return false;
}

void DFS(int row, int col)
{
	for(int i = 0; i < 4; i++)
	{
		int r = row + drow[i];
		int c = col + dcol[i];
		if(r >= 0 && r < n && c >= 0 && c < m && Mark[r][c] == 0
		&& (i == Matrix[row][col] || Check(i, r, c)))
		{
			Mark[r][c] = 1;
			DFS(r,c);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
//	freopen("input.txt","r",stdin);
	cnt = 0;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		char temp[MAX];
		cin >> temp;
		for(int j = 0; j < m; j++)
		{
			if(temp[j] == 'W') Matrix[i][j] = W;
			else if(temp[j] == 'N') Matrix[i][j] = N;
			else if(temp[j] == 'E') Matrix[i][j] = E;
			else if(temp[j] == 'S') Matrix[i][j] = S;
			Mark[i][j] = 0;
		}
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
		{
			if(Mark[i][j] == 0)
			{
				Mark[i][j] = 1;
				DFS(i,j);
				cnt++;
			}
		}
	cout << cnt << endl;
	return 0;
}