描述

迢迢牵牛星，皎皎河汉女。

纤纤擢素手，札札弄机杼；

终日不成章，泣涕零如雨。

河汉清且浅，相去复几许？

盈盈一水间，脉脉不得语。

——《古诗十九首》

传说，上古时期的某个七月七日，王母娘娘为了阻止牛郎织女的爱情，划一道玉钗拆散鸳鸯，使两人“星桥鹊驾，经年才见，想离情、别恨难穷。”于是，“执子之手，与子偕老”成了天下有情人共同的希翼。

在气宇轩昂、玉树临风、才高八斗、英俊潇洒的程文大牛的期盼中，浪漫又迷人的七夕终于来临了。迷离的夜空之上，牛郎织女的絮语伴随着美好的秋光，浸润了古今文人墨客多情的心。他与美若天仙、唇红齿白、蕙质兰心、冰雪聪明的某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

输出样例 1

2

题解：

//
//  main.cpp
//
//
//  Created by Edwin on 2019/2/25.
//  Copyright © 2019 Edwiv. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
const int maxn=2000;
using namespace std;
int n,m;
char Map[maxn][maxn];
int d[maxn],c[maxn];
bool vis[maxn];
int dirx[4]={1,-1,0,0};
int diry[4]={0,0,1,-1};
int check(int x,int y){
    if(x<0||x>=n||y<0||y>=m)
        return 0;
    return 1;
}
struct edge{
    int v,w,nxt;
}e[maxn];
int tot,head[maxn];
void init(){
    mst(head,-1);
    tot = 0;
}
void addedge(int u,int v,int w){
    e[tot] = {v,w,head[u]}; head[u] = tot++;
}
int Spfa(int s,int n){
    int u,v,w;
    queue <int> q;
    mst(d,INF);mst(c,0);mst(vis,0);
    d[s]=0;
    q.push(s); vis[s]=1; c[s]=1;
    while(!q.empty()){
        u=q.front(); q.pop(); vis[u]=0;
        for(int k=head[u]; k!=-1; k=e[k].nxt){
            v=e[k].v, w=e[k].w;
            if( d[u]+w < d[v]){
                d[v]=d[u]+w;
                if(!vis[v]){
                    q.push(v); vis[v]=1;
                    if(++c[v]>n)
                        return 0;
                }
            }
        }
    }
    return 1;
}

int main(){
    sc2(n,m);
    getchar();
    init();
    FF(i,n){
        FF(j,m){
            scanf("%c",&Map[i][j]);
        }
        getchar();
    }
    FF(i,n){
        FF(j,m){
            for(int k=0;k<4;++k){
                int tox=i+dirx[k];
                int toy=j+diry[k];
                if(check(tox,toy)){
                    if(Map[tox][toy]==Map[i][j])
                        addedge(i*m+j+1,tox*m+toy+1,0);
                    else
                        addedge(i*m+j+1,tox*m+toy+1,1);
                }
            }
        }
    }
    int s=0;
    int t=n*m+1;
    for(int i=0;i<m;++i){
        addedge(s,i+1,0);
        addedge((n-1)*m+i+1,t,0);
    }
    Spfa(s,n*m+2);
    printf("%d\n",d[t]+1);
    return 0;
}