B古韵之鹊桥相会【noip模拟赛1】

发表于 | 分类于 ， | 阅读量 次

描述

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

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

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

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

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

——《古诗十九首》

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

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

来源：
来自 <http://www.dingbacode.com/contest/19/problem/B>

题解：
dfs搜索或最短路

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
dfs：
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3fffffff

int walk[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
int Min;
int n,m;
char mp[25][25];
int w[25][25];

void dfs(int H,int L,int step)
{
    if(w[H][L]<=step) return;

    w[H][L]=step;

    for(int i=0; i<4; i++)
    {
        int h=H+walk[i][0];
        int l=L+walk[i][1];

        if(h<0||h>=n||l<0||l>=m)
            continue;

        int ju;
        if(mp[h][l]==mp[H][L]) ju=step;
        else ju=step+1;


        if(w[h][l]<ju) continue;
        dfs(h,l,ju);

    }
    return;
}



int main ( )
{


    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>mp[i];

    Min=INF;

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            w[i][j]=INF;


    for(int i=0; i<m; i++)
    {
        dfs(0,i,1);
    }

    for(int i=0; i<m; i++)
        Min=min(Min,w[n-1][i]);
    cout<<Min<<endl;

    return 0;
}