Alphabet Path

Time limit2sMemory limit256 MB

Summary

Find the longest path from the top-left cell of a grid moving to adjacent cells while never revisiting a letter already used, maximizing visited cells.

Level: Medium5 of 10
Topics: Backtracking, DFS, Brute force
Solved: No attempts yet

Problem

A board has $R$ rows and $C$ columns. Each cell contains one uppercase English letter. A piece starts in the upper-left cell, row $1$ and column $1$ .

The piece may move to one vertically or horizontally adjacent cell. It may enter a cell only if that cell's letter is different from every letter on the cells visited so far. In other words, the path cannot contain the same letter twice.

Find the maximum number of cells the piece can visit, including the starting cell.

Input

The first line contains $R$ and $C$ , separated by a space. ( $1 \le R,C \le 20$ )

Each of the next $R$ lines contains $C$ uppercase English letters with no spaces, describing the board.

Output

Print the maximum number of cells the piece can visit.

Examples3

Example 1
Input
```
2 4
CAAB
ADCB
```
Expected output
```
3
```
Example 2
Input
```
3 6
HFDFFB
AJHGDH
DGAGEH
```
Expected output
```
6
```
Example 3
Input
```
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
```
Expected output
```
10
```