题目描述(ID:12051)
标题: 探宝
标签: 图结构
详情:
淘淘得到了一个神秘地图,准备去探宝。仔细个观察这个地图,发现自己必须从上到下打通一条道路才能到达目的地(能够从第一行到最后一行即可),于是淘淘决定用排云掌和风神腿打开前方的道路。
现用不同的字母来表示不同颜色的星星,连在一起(水平或竖直相邻才算连在一起)的相同颜色的星星,淘淘可以一次性全部打掉。
图样如下:
AABBCCD
AFFBGGD
IIJBKKD
MNNOOPD
QQRRSST
比如在这张地图中,淘淘可以先打掉最右边的D区域,然后再打通T区域,这样就只用两次就可以打通道路(道路是可以拐弯的,不一定要是一条直线)。
因为使用排云掌和风神腿会耗费体力,所以淘淘想用最少的次数来打通这条道路,这件事就交给你了。
输入格式:
第一行有两个整数,m和n(0
输出格式:
一个整数,淘淘打通道路用功力的最少的次数。
样例:

输入

5 7
AABBCCD
EFFGGHH
IIJJKKL
MNNOOPP
QQRRSST

输出

5

输入

6 7
ABCDEAB
ABCFEAB
AEAABAB
ACDAEEB
FFGAHIJ
KLMANOP

输出

2

解释

先从第一行打通C区域,在接着打通A区域,即可到达最后一行。
登录并解答