SPOJ.COM - Thuật toán bài ABCPATH - ABC Path

#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;
}