HUST Past Monthly Hard Problems Challenge Contest (1)

From: 2011-05-13 12:00:00 To: 2011-05-13 17:00:00 Now: 2017-09-20 01:07:52 Status: Public

H - dangerous

Time Limit: 3s Memory Limit: 128MB

Submissions: 63 Solved: 6
Description
Isun is in danger,he needs your help. Isun lost his way in an area controlled by a lot of monster.Isun can just go up , down, left and right in this area. This area is made up of N*M small squares with the same size(N lines ,each line with M squares) . Each square is marked by a number from 0 to 9. Squares with same edge and marked with same number is controlled by same monster. If two neighbor squares are controlled by two different monster , he can just pass between them without being discovered by the monster(he will be discovered other case) . Isun wants to know the minimum number of monsters he must encountered in order to go out of the area. The position Isun stays now has no monster(ie. the number in the grid where Isun stays now is neglected). Isun doesn't know where he is at all , so he wants to know the answer in the worst situation . Please help him.
Input
Input have multiple test cases and terminates with EOF. Each case has the form as followed. The first line of the input contains integer numbers N, M (1 ≤ N, M ≤ 500). The map followed. The map is written in the form of N lines with M numbers from 0 to 9 in each line. Numbers in a line are written one after another without spaces.
Output
For each case output one number indicating the number of monster Isun had to fight with.
Sample Input
3 3
111
121
111
7 6
200320
011022
018100
018111
201191
020011
002020
7 7
1111111
1222221
1211121
1212121
1211121
1222221
1111111
5 5
11111
11111
11211
11111
11111
Sample Output
1
1
3
1
Hint
There are two monsters in the area marked with the number 1(one has 4 squares, another has 9 squares). There is one dangerous square (marked with the number 9) besides the regions in possession of monsters. Note that squares marked with the number 8 are not dangerous, as they do not satisfy the definition of a dangerous square.
Source
Wu Shaoliang