Created
September 15, 2018 01:38
Star
You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment