408772: GYM103306 G Grid of Letters

John likes to solve the word search puzzles that appear in the newspaper he reads while drinks his coffee. A word search puzzle consists of the letters of words placed in a grid, which usually has a rectangular or square shape. The objective of the game is to find and mark the words from a list in the grid, these words may be placed horizontally, vertically, or diagonally.

John has a lot of experience solving the puzzles and he finds it kind of boring now, he decided to play a different puzzle on the same grid. Instead of searching for words, he will search for the longest path of consecutive letters he can find in the grid, the path can be followed from one letter to the other if the letters are adjacent in any direction (horizontally, vertically, or diagonally). For example, if John has the following grid

The longest path of consecutive letters he can find in the grid is conformed with the letter 'CDEFGH', in the following positions:

John has told you his new puzzle idea, your response was it is even easier than word search, to demonstrate this to him, you decided to write a program that finds the length of the longest path of consecutive letters John can find in a word search grid.

The first line of input contains two integer numbers separated by a space $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 1000$$$), representing the number of rows and columns in the grid. The next $$$N$$$ lines contains a string with $$$M$$$ characters, the $$$j$$$-th character of the $$$i$$$-th line, represents ths character at the $$$i$$$-th line and $$$j$$$-th column of the grid. All characters in the grid will be uppercase letters from the english alphabet.

Output a line containing a single integer, the length of the longest path of consecutive letters that can be found in the grid.

4 3
ABH
FFG
BDE
AFC

6

3 3
AZC
YBC
ABC

3