Minimum Number of Escaping Animals

During their escape, a group of animals must cross a rectangular region of size \(R \times C\). All animals enter the region at the top‐left cell (cell \((1,1)\)) and exit at the bottom‐right cell (cell \((R,C)\)). They escape one by one. Each animal walks along an arbitrary path moving in the four cardinal directions (up, down, left, right). In particular, an animal does not necessarily choose the shortest route and may even visit the same cell several times (including the entrance and the exit).

Every time an animal steps on a cell, it leaves its own footprint (represented by a unique uppercase letter). If the cell already has a footprint, the animal erases the old footprint and writes its own. Thus, in the final pattern, each cell contains the footprint of the last animal that visited it.

Important note: Since every animal begins at cell \((1,1)\) and ends at \((R,C)\), the final footprints at these two cells must be the mark of the last animal. In other words, the characters in the top‐left and bottom‐right cells are identical.

Your task is: Given the final pattern of footprints on the \(R\times C\) grid, determine the minimum number of animals that may have escaped.

Explanation

Since each animal uses a unique mark, the final footprint in any cell is the mark of the animal that visited that cell last. Notice that if a cell’s final mark does not match the mark in the entrance (which is the same as the exit), then that cell was never visited by the last animal. In order for the final configuration to be produced, the marks you see in the grid must come from a subsequence of the animals that actually left surviving footprints. It turns out that it is always possible to explain the pattern with exactly as many animals as there are distinct characters in the grid. (Any animal whose mark does not appear in the final grid can be ignored.)

Thus, the answer is simply the number of distinct characters in the grid.

inputFormat

The first line contains two integers \(R\) and \(C\) \((2 \le R, C \le 100)\) --- the number of rows and columns of the grid.

Each of the following \(R\) lines contains a string of exactly \(C\) uppercase letters. It is guaranteed that the characters in the top-left cell (first character of the first line) and the bottom-right cell (last character of the last line) are identical.

outputFormat

Output a single integer --- the minimum number of animals that must have escaped.

sample

3 3
AAA
ABA
AAA

2