Vijos - 古韵之鹊桥相会(最短路||DFS)

题目描述

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

输入格式

第一行有两个整数，m和n（0<m,n<21）；
下面m行，每行n个字母。

输出格式

一个整数，程文打通道路用功力的最少的次数。

样例输入

5 7
AABBCCD
AFFBGGD
IIJBKKD
MNNOOPD
QQRRSST

样例输出

2

解题思路

这道题可以用最短路做，也可以搜索。最短路的话主要就是建图的问题，最短路哪个都行，Dijkstra、Floyd、SPFA...不过还是感觉DFS比较简单一些，数据也并不是很大。
Dijkstra:

#include <stdio.h>
#define MAXN 25
const int inf = 99999999;
char a[MAXN][MAXN];
int n, m, vis[MAXN * MAXN], dis[MAXN * MAXN], map[MAXN * MAXN][MAXN * MAXN];
void Dijkstra(int s)
{
    int k, minn;
    for (int i = 0; i < n * m; i++)
    {
        vis[i] = 0;
        dis[i] = inf;
    }
    dis[s] = 0;
    for (int i = 0; i < n * m; i++)
    {
        k = s;
        minn = inf;
        for (int j = 0; j < n * m; j++)
            if (!vis[j] && minn > dis[j])
                minn = dis[k = j];
        vis[k] = 1;
        for (int j = 0; j < n * m; j++)
            if (map[k][j] < inf)
                if (!vis[j] && dis[j] > dis[k] + map[k][j])
                    dis[j] = dis[k] + map[k][j];
    }
}
int main()
{
    int minn;
    while (~scanf("%d%d", &n, &m))
    {
        minn = inf;
        for (int i = 0; i < n * m; i++)
            for (int j = 0; j < n * m; j++)
                    map[i][j] = inf;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                scanf(" %c", &a[i][j]);
                if (i)
                {
                    if (a[i - 1][j] != a[i][j])
                        map[(i - 1) * m + j][i * m + j] = map[i * m + j][(i - 1) * m + j] = 1;
                    else map[(i - 1) * m + j][i * m + j] = map[i * m + j][(i - 1) * m + j] = 0;
                }
                if (j)
                {
                    if (a[i][j - 1] != a[i][j])
                        map[i * m + j - 1][i * m + j] = map[i * m + j][i * m + j - 1] = 1;
                    else map[i * m + j - 1][i * m + j] = map[i * m + j][i * m + j - 1] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++)
        {
            Dijkstra(i);
            for (int j = (n - 1) * m; j < n * m; j++)
                if (minn > dis[j])
                    minn = dis[j];
        }
        printf("%d\n", minn + 1);
    }
    return 0;
}

DFS:

#include <stdio.h>
char a[25][25];
int n, m, map[25][25];
const int inf = 0x7fffffff;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void DFS(int x, int y, int step)
{
    int tx, ty, s;
    if (map[x][y] <= step)
        return;
    map[x][y] = step;
    for (int i = 0; i < 4; i++)
    {
        tx = x + dir[i][0];
        ty = y + dir[i][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m)
        {
            if (a[tx][ty] != a[x][y])
                s = step + 1;
            else s = step;
            DFS(tx, ty, s);
        }
    }
}
int main()
{
    int minn;
    while (~scanf("%d %d", &n, &m))
    {
        minn = inf;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                map[i][j] = inf;
        for (int i = 0; i < n; i++)
            scanf("%s", a[i]);
        for (int i = 0; i < m; i++)
            DFS(0, i, 1);
        for (int i = 0; i < m; i++)
            if (minn > map[n - 1][i])
                minn = map[n - 1][i];
        printf("%d\n", minn);
    }
    return 0;
}