Created
September 15, 2018 01:25
-
-
Save completejavascript/ae79cfac0652cf5b6c8d253adb0909e3 to your computer and use it in GitHub Desktop.
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 = 51; | |
int H; // Lưu chiều cao lưới | |
int W; // Lưu chiều rộng lưới | |
int Answer; // Kết quả đường đi dài nhất | |
char Matrix[MAX][MAX]; // Lưu lưới các kí tự | |
bool Visit[MAX][MAX]; // Đánh dấu trạng thái kí tự được 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 : là chỉ số hàng của điểm hiện tại | |
* col : là chỉ số cột của điểm hiện tại | |
* leng: là độ dài đường đi hiện tại | |
*/ | |
void Start(int row, int col, int leng) | |
{ | |
// Kiểm tra 8 hướng kề với điểm hiện tại. | |
for(int i = 0; i < 8; i++) | |
{ | |
int r = row + drow[i]; | |
int c = col + dcol[i]; | |
/* | |
* Ô tiếp theo nhảy tới phải thoả mãn điều kiện: | |
* Nằm trong ma trận | |
* Chưa được thăm | |
* Phải là kí tự kế tiếp của kí tự hiện tại theo thứ tự A,B,C,... | |
*/ | |
if (r >= 0 && r < H && c >= 0 && c < W && | |
Visit[r][c] == 0 && Matrix[r][c] == Matrix[row][col] + 1) | |
{ | |
Visit[r][c] = 1; | |
Start(r, c, leng+1); | |
} | |
} | |
// Khi không thể đi được nữa, ta sẽ cập nhật kết quả | |
if(leng > Answer) | |
{ | |
Answer = leng; | |
} | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
// comment dòng này trước khi submit | |
freopen("input.txt","r",stdin); | |
int tc = 0; | |
while(true) | |
{ | |
// Nhập đầu vào | |
cin >> H >> W; | |
if(H == 0 && W == 0) break; | |
tc++; | |
Answer = 0; | |
for(int i = 0; i < H; i++) | |
cin >> Matrix[i]; | |
for(int i = 0; i < H; i++) | |
for(int j = 0; j < W; j++) | |
Visit[i][j] = false; | |
// Tìm kiếm kí tự 'A', và bắt đầu tìm đường đi từ đó | |
for(int i = 0; i < H; i++) | |
for(int j = 0; j < W; j++) | |
if(Matrix[i][j] == 'A') | |
{ | |
Visit[i][j] = true; | |
// Bắt đầu tại điểm có toạ độ (i, j) và độ dài đường đi lúc này là 1 | |
Start(i, j, 1); | |
} | |
// In kết quả | |
cout << "Case " << tc << ": " << Answer << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment