URI Online Judge | 1234

The Half-Blood Prince

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 8

This year, instead of submit themselves to humbling initiation rituals, the freshmen of the Computer Science undergraduate course have chosen to do something more humanitarian to celebrate their entry into a federal university. First, they have gone to donate blood at HEMOSC, the blood centre of the state of Santa Catarina. Then, still with half of the blood in the body, they have gone to a public school, the Little Prince Municipal Centre of Childhood Education (or just Little Prince), in order to do voluntary works. In one of the developed activities, the children of the school should play a very interesting single-player computer game named Flood It!.

In Flood It!, it is presented to the player a grid N × M in which each cell is coloured with one colour, as in the figure to the left. When the player clicks on any cell of the grid of colour α, the cell in the top-leftmost corner of the grid, called source, of colour β, receives the colour α, but not only it: all those cells which are connected to the source by paths which use only the colours α or β also receive the colour α. The adjacencies between cells should be considered only in the horizontal and vertical directions to form the paths. For example, when the player clicks on the cell highlighted in the figure to the left, the grid receives the colouring of the figure to the right. The goal of the game is to make the grid monochromatic.

    

Input

The first line of the input consists of 2 integers N and M (1 ≤ N ≤ 4, 1 ≤ M ≤ 5), which represent respectively the number of lines and the number of columns of the grid. The N lines following describe the initial configuration of the grid, representing each colour by an integer between 0 and 9. The input does not consist of any other line.

Output

Print a line containing a single integer that represents the minimum number of clicks that the player must do in order to make the grid monochromatic. Be careful! We have been generous while defining the test cases and the time limit of this problem, but not so much.

Input Samples Output Samples

4 5
00162
30295
45033
01837

10

4 5
01234
12345
23456
34567

7

4 5
01234
34567
67890
90123

12