Longest Alphabetical Path

You are given an \(N \times N\) grid filled with uppercase English letters. Your task is to find the length of the longest path where each consecutive letter in the path is exactly the next letter in the alphabet. In other words, if a cell contains the letter \(c\), you can move to an adjacent cell (in any of the 8 possible directions: horizontally, vertically, or diagonally) only if it contains the letter \(c+1\). Each cell may be visited only once in a given path.

The problem requires you to determine the maximum length among all possible paths that satisfy the above condition. For example, in the grid below:

A B C D
Z Y X W
A B C D
B C D E

One of the longest valid paths is of length 5.

Note: The alphabetical order follows the standard order of the English alphabet where \(A \rightarrow B \rightarrow C \rightarrow \ldots\).

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains an integer \(N\) representing the size of the grid.
2. The next \(N\) lines each contain \(N\) uppercase English letters separated by spaces, representing the grid rows.

outputFormat

Output a single integer to standard output (stdout) representing the length of the longest alphabetical path in the grid.

4
A B C D
Z Y X W
A B C D
B C D E

5