SPOJ.COM - Thuật toán bài LABYR1 - Labyrinth

Posted on November 7th, 2016

Đề bài:

Phía bắc của kim tự tháp chứa một mê cung rất lớn và phức tạp. Mê cung được chia thành những khối hình vuông, mỗi phần trong chúng được phủ bởi đá hoặc để trống. Có những cái móc nhỏ ở giữa mỗi khu vực trống. ACM phát hiện ra rằng 2 cái móc phải được kết nối với nhau bằng dây thừng, chạy xuyên qua những cái móc ở mỗi khu trống, trên đường nối giữa những cái được kết nối với nhau. Khi những cái thừng được gắn chặt thì một cánh cửa bí mật sẽ được mở ra. Vấn đề đặt ra là chúng ta không biết những cái móc nào để kết nối. Điều đó cũng có nghĩa là độ dài cần thiết của dây thừng cũng không biết. Nhiệm vụ của bạn là tìm ra độ dài lớn nhất có thể của dây cần thiết.

Đầu vào

Dòng đầu tiên là số T - số lượng test case. Mỗi test case bao gồm 2 số C và R (3 <= C,R <= 1000) là số cột và số hàng. Sau đó là R dòng, mỗi dòng bao gồm C kí tự. Những kí tự này xác định ra mê cung. Mỗi cái trong chúng là '#' hoặc '.'. Trong đó, ## miêu tả đá, còn dấu . miêu tả khu vực trống. Biết rằng chỉ có thể di chuyển giữa những khu vực kề nhau (khu vực kề nhau là khu vực có cạnh chung). Không thể di chuyển chéo và cũng không thể đi ra ngoài mê cung.

Mê cung được thiết kế sao cho chỉ có chính xác 1 đường giữa 2 khu vực trống. Do đó, nếu như tìm thấy những cái móc thích hợp thì rất dễ để tìm ra đường đúng để nối chúng.

Đầu ra

Mỗi test case in ra trên 1 dòng duy nhất, theo dạng sau:

Maximum rope length is X.

Trong đó, x là độ dài đường dài nhất giữa 2 khu vực trống.

Ví dụ

Đầu vào:

2
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######

Đầu ra:

Maximum rope length is 0.
Maximum rope length is 8.

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

Phân tích

  • Bài toán sử dụng thuật toán tìm kiếm theo chiều rộng BFS để giải quyết. Cụ thể là mình sẽ áp dụng 2 lần BFS.

  • Lần thứ nhất mình sử dụng BFS tại một điểm bất kì. Từ đó tìm ra được điểm có khoảng cách xa nhất so với điểm bắt đầu.

  • Tiếp tục sử dụng thuật toán BFS tại điểm vừa tìm được. Mình lại tìm được điểm có khoảng cách xa nhất so với điểm bắt đầu trong trường hợp thứ hai này. Lần này, khoảng cách xa nhất chính là cái cần tìm.

  • Thực chất đây là thuật toán tìm đường đi dài nhất trên cây.

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 MAX_QUEUE = MAX*MAX;

int C, R, T, Answer, SR, SC;
int Matrix[MAX][MAX], Mark[MAX][MAX];

typedef struct
{
	int row;
	int col;
}Point;

Point queue[MAX_QUEUE];
int fr, re, leng;

void Enqueue(int row, int col)
{
	Point p;
	p.row = row;
	p.col = col;

	queue[re] = p;
	re = (re + 1) % MAX_QUEUE;
	leng++;
}

Point Dequeue()
{
	Point p = queue[fr];
	fr = (fr + 1) % MAX_QUEUE;
	leng--;
	return p;
}

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

// BFS tại điểm (row, col) tới tất cả các điểm còn lại
void BFS(int row, int col)
{
	for(int i = 0; i < R; i++)
		for(int j = 0; j < C; j++)
			Mark[i][j] = 0;

	fr = re = leng = 0;
	Enqueue(row, col);
	Mark[row][col] = 1;

	while(leng > 0)
	{
		Point p = Dequeue();
		for(int i = 0; i < 4; i++)
		{
			int r = p.row + drow[i];
			int c = p.col + dcol[i];
			if(r >= 0 && r < R && c >= 0 && c < C && 
				Mark[r][c] == 0 && Matrix[r][c] == 1)
			{
				Mark[r][c] = Mark[p.row][p.col] + 1;
				Enqueue(r,c);
			}
		}
	}
}

// Tìm điểm có khoảng cách xa nhất so với điểm xét ban đầu.
void FindMax()
{
	for(int i = 0; i < R; i++)
		for(int j = 0; j < C; j++)
			if(Mark[i][j] > Answer)
			{
				Answer = Mark[i][j];
				SR = i;
				SC = j;
			}
}

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

	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		Answer = SR = SC = 0;
		cin >> C >> R;
		for(int i = 0; i < R; i++)
		{
			char temp[MAX];
			cin >> temp;
			for(int j = 0; j < C; j++)
			{
				if(temp[j] == '#') Matrix[i][j] = 0;
				else if(temp[j] == '.')
				{
					Matrix[i][j] = 1;
					SR = i;
					SC = j;
				}
			}
		}

		BFS(SR,SC);
		FindMax();

		BFS(SR,SC);
		FindMax();

		cout << "Maximum rope length is " << Answer - 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!