dangerous
Time Limit : 3 Second
Memory Limit : 128 MB
Submission: 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