題目鏈接:https://vijos.org/p/1406

題目描述

迢迢牽牛星，皎皎河漢女。
纖纖擢素手，札札弄機杼；
終日不成章，泣涕零如雨。
河漢清且淺，相去復幾許？
盈盈一水間，脈脈不得語。
——《古詩十九首》
傳說，上古時期的某個七月七日，王母娘娘為了阻止牛郎織女的愛情，劃一道玉釵拆散鴛鴦，使兩人“星橋鵲駕，經年才見，想離情、別恨難窮。”于是，“執子之手，與子偕老”成了天下有情人共同的希翼。
在氣宇軒昂、玉樹臨風、才高八斗、英俊瀟灑的程文大牛的期盼中，浪漫又迷人的七夕終于來臨了。迷離的夜空之上，牛郎織女的絮語伴隨著美好的秋光，浸潤了古今文人墨客多情的心。他與美若天仙、唇紅齒白、蕙質蘭心、冰雪聰明的某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; }

總結

以上是生活随笔為你收集整理的Vijos - 古韵之鹊桥相会(最短路||DFS)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。