SPOJ.COM - Thuật toán bài ALLIZWEL - ALL IZZ WELL
Đề 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
Các 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 DFS và vét cạn.
Lời giải:
(Các 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 tôi 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 tôi 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 các 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; | |
| } | |
| } |
Code by Phạm Văn Lâm