SPOJ.COM - Thuật toán bài ALLIZWEL - ALL IZZ WELL

Posted on September 23rd, 2016

Đề bài:

Mr.Giang luôn luôn nói "ALL IZZ WELL" mỗi khi anh ấy gặp rắc rối. Vì vậy, bạn bè và mọi người xung quanh luôn luôn cười anh ta. Tuy nhiên, Mr.Giang luôn tin vào niềm tin của mình. Anh ấy tin rằng cụm từ "ALLIZZWELL" sẽ làm mọi việc được giải quyết ổn thoả.

Nhiệm vụ của bạn là tạm bỏ qua câu truyện trên và tìm ra nếu như có đường đi trên ma trận tạo thành câu "ALLIZZWELL". Biết rằng có đường đi từ một cell đến tất cả các cell kề với nó. Hai cell kề nhau nếu chúng chia sẻ cạnh hoặc góc.

Đầu vào

Dòng đầu tiên bao gồm một số T biểu diễn số lượng test case. Dòng đầu tiên của mỗi test case bao gồm 2 số R và C biểu diễn số dòng và số cột của ma trận. Cuối cùng là miêu tả ma trận.

Đầu ra

Với mỗi test case, in ra "YES" nếu như có đường đi tạo thành "ALLIZZWELL". Ngược lại in ra "NO"

Chú ý: - Cẩn thận với test case số 4 - Có một dòng mới sau mỗi test case trong đầu vào

Ràng buộc:

T <= 1000 
R <= 100 
C <= 100

Ví dụ

Đầu vào:

5 
3 6 
AWE.QX 
LLL.EO 
IZZWLL 
1 10 
ALLIZZWELL 
2 9 
A.L.Z.E.. 
.L.I.W.L. 
3 3 
AEL 
LWZ 
LIZ 
1 10 
LLEWZZILLA 

Đầu ra:

YES 
YES 
NO 
NO 
YES 

Bạn có thể tham khảo đề bài tiếng anh và submit tại đây: http://www.spoj.com/problems/ALLIZWEL/

Phân tích

Bài toán này tương tự như bài toán ABCPATH. Tuy nhiên, đối với bài toán ABCPATH, đường đi là các kí tự phân biệt A, B, C,...Z. Còn với bài toán này, đường đi là "ALLIZZWELL", trong đó các kí tự có thể lặp lại. Do đó, ta phải kiểm tra tất cả các đường đi có thể bắt đầu từ kí tự 'A'.

Đó chính là thuật toán tìm kiếm theo chiều sâu DFSVét cạn - Brute Force.

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 = 105;
const char Array[] = "ALLIZZWELL";

int  R, C;              // Lưu số lượng hàng và cột ở ma trận
int  Answer;            // Lưu kết quả của bài toán
char Matrix[MAX][MAX];  // Ma trận đầu vào
bool Visit[MAX][MAX];   // Đánh dấu trạng thái là thăm hay chưa.

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

/*
* row, col lần lượt là hàng và cột đang xét
* current là chỉ số của kí tự hiện tại trong mảng Array[] = "ALLIZZWELL"
* chỉ số bắt đầu từ 0 và cuối cùng là 9
*/
void Start(int row, int col, int current)
{
	// Nếu tìm được đường đi
	if(current == 9)
	{
		Answer = 1;
		return;
	}

	// Kiểm tra 8 hướng kề với ô đang xét
	for(int i = 0; i < 8; i++)
	{
		int r = row + drow[i];
		int c = col + dcol[i];

		/*
		* Ô nhảy được tới phải là ô trong ma trận
		* Chưa được thăm 
		* Và là kí tự tiếp theo trong mảng Array[] trên
		*/
		if (r >= 0 && r < R && c >= 0 && c < C &&
			!Visit[r][c] && Matrix[r][c] == Array[current+1])
		{
			Visit[r][c] = true;
			Start(r, c, current+1);
			Visit[r][c] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);

	// comment trước khi submit
	freopen("input.txt","r",stdin);

	int T;
	cin >> T;

	for(int tc = 0; tc < T; tc++)
	{
		Answer = 0;

		cin >> R >> C;
		for(int i = 0; i < R; i++)
			cin >> Matrix[i];

		for(int i = 0; i < R; i++)
			for(int j = 0; j < C; j++)
				Visit[i][j] = false;

		// Tìm tất cả các kí tự A trong ma trận và tìm đường đi từ đó
		for(int i = 0; i < R; i++)
		{
			for(int j = 0; j < C; j++)
				if(Matrix[i][j] == 'A')
				{
					Visit[i][j] = true;
					Start(i, j, 0);
					Visit[i][j] = false;

					// Nếu đã tìm được đường đi thoả mãn thì thoát luôn.
					if(Answer) break;
				}

			if(Answer) break;
		}

		// In ra kết quả
		cout << endl;
		if(Answer) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

★ 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!