描述
迢迢牵牛星，皎皎河汉女。
纤纤擢素手，札札弄机杼；
终日不成章，泣涕零如雨。
河汉清且浅，相去复几许？
盈盈一水间，脉脉不得语。
——《古诗十九首》
传说，上古时期的某个七月七日，王母娘娘为了阻止牛郎织女的爱情，划一道玉钗拆散鸳鸯，使两人“星桥鹊驾，经年才见，想离情、别恨难穷。”于是，“执子之手，与子偕老”成了天下有情人共同的希翼。
在气宇轩昂、玉树临风、才高八斗、英俊潇洒的程文大牛的期盼中，浪漫又迷人的七夕终于来临了。迷离的夜空之上，牛郎织女的絮语伴随着美好的秋光，浸润了古今文人墨客多情的心。他与美若天仙、唇红齿白、蕙质兰心、冰雪聪明的某MM约好在清江的小桥上相会……
天亦有情，此时，浮云错开，从天而降一张丝绸地图：正面上，不同颜色的星星组成了前方道路的俯视图；背面写着“愿有情人终成眷属，无伴者皆得幸福。——瑾姝”。
程文仔细看着这个图，发现自己必须从上到下打通一条道路才能见到某MM，于是程文决定用排云掌和风神腿打开前方的道路——
现用不同的字母来表示不同颜色的星星，连在一起(水平或竖直相邻才算连在一起)的相同颜色的星星，程文可以一次性全部打掉。图样如下：
AABBCCD
AFFBGGD
IIJBKKD
MNNOOPD
QQRRSST
比如在这张地图中，程文可以先打掉最右边的D区域，然后再打通T区域，这样就只用两次就可以打通道路(道路是可以拐弯的，不一定要是一条直线)。
因为使用排云掌和风神腿会耗费体力，耗费干净了程文就没法陪MM一起玩了，所以程文想用最少的次数来打通这条道路，不过程文现在跑去学Java了，这件事就交给你了。
输入
第一行有两个整数，m和n（0<m,n<21）；
下面m行，每行n个字母。
输出
一个整数，程文打通道路用功力的最少的次数。
输入样例 1
5 7 AABBCCD AFFBGGD IIJBKKD MNNOOPD QQRRSST
相邻的格子间若字母相同连0的边 不相同连1的边 然后floyd 或者dijkstra
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define N 400+5 int map[N][N],n,m; char str[N][N]; void check(int i,int j,int cnt) { if (str[i][j]==str[i][j+1]&&j+1<=m) map[cnt][cnt+1]=map[cnt+1][cnt]=0; else if(str[i][j]!=str[i][j+1]&&j+1<=m) map[cnt][cnt+1]=map[cnt+1][cnt]=1; if (str[i][j]==str[i][j-1]&&j-1>0) map[cnt][cnt-1]=map[cnt-1][cnt]=0; else if(str[i][j]!=str[i][j-1]&&j-1>0) map[cnt][cnt-1]=map[cnt-1][cnt]=1; if (str[i][j]==str[i-1][j]&&i-1> 0&&cnt-m>0) map[cnt][cnt-m]=map[cnt-m][cnt]=0; else if(str[i][j]!=str[i-1][j]&& i-1>0 && cnt-m>0) map[cnt][cnt-m]=map[cnt-m][cnt]=1; if (str[i][j]==str[i+1][j]&&i+1<=n) map[cnt][cnt+m]=map[cnt+m][cnt]=0; else if(str[i][j]!=str[i+1][j]&&i+1<=n) map[cnt][cnt+m]=map[cnt+m][cnt]=1; } int main() { cin>>n>>m; int cnt=0; memset(map,0x3f,sizeof map); for(int i=1;i<=n;++i) scanf("%s",str[i]+1); for(int i=1;i<=m;++i) map[cnt][i]=0; int end=n*m+1; for(int i=(n-1)*(m)+1;i<=n*m;++i) map[i][end]=0; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) check(i,j,++cnt); for(int k=0;k<=cnt+1;++k) for(int i=0;i<=cnt+1;++i) for(int j=0;j<=cnt+1;++j) map[i][j]=min(map[i][j],map[i][k]+map[k][j]); cout<<map[0][end]+1; }