描述

?

迢迢牽牛星，皎皎河漢女。

纖纖擢素手，札札弄機杼；

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

河漢清且淺，相去復幾許？

盈盈一水間，脈脈不得語。

——《古詩十九首》

傳說，上古時期的某個七月七日，王母娘娘為了阻止牛郎織女的愛情，劃一道玉釵拆散鴛鴦，使兩人“星橋鵲駕，經(jīng)年才見，想離情、別恨難窮。”于是，“執(zhí)子之手，與子偕老”成了天下有情人共同的希翼。

在氣宇軒昂、玉樹臨風、才高八斗、英俊瀟灑的程文大牛的期盼中，浪漫又迷人的七夕終于來臨了。迷離的夜空之上，牛郎織女的絮語伴隨著美好的秋光，浸潤了古今文人墨客多情的心。他與美若天仙、唇紅齒白、蕙質(zhì)蘭心、冰雪聰明的某MM約好在清江的小橋上相會……

天亦有情，此時，浮云錯開，從天而降一張絲綢地圖：正面上，不同顏色的星星組成了前方道路的俯視圖；背面寫著“愿有情人終成眷屬，無伴者皆得幸福。——瑾姝”。

程文仔細看著這個圖，發(fā)現(xiàn)自己必須從上到下打通一條道路才能見到某MM，于是程文決定用排云掌和風神腿打開前方的道路——

現(xiàn)用不同的字母來表示不同顏色的星星，連在一起(水平或豎直相鄰才算連在一起)的相同顏色的星星，程文可以一次性全部打掉。圖樣如下：

AABBCCD

AFFBGGD

IIJBKKD

MNNOOPD

QQRRSST

比如在這張地圖中，程文可以先打掉最右邊的D區(qū)域，然后再打通T區(qū)域，這樣就只用兩次就可以打通道路(道路是可以拐彎的，不一定要是一條直線)。

因為使用排云掌和風神腿會耗費體力，耗費干凈了程文就沒法陪MM一起玩了，所以程文想用最少的次數(shù)來打通這條道路，不過程文現(xiàn)在跑去學Java了，這件事就交給你了。

?

輸入

?

第一行有兩個整數(shù)，m和n（0<m,n<21）；

下面m行，每行n個字母。

?

輸出

?

一個整數(shù)，程文打通道路用功力的最少的次數(shù)。

?

輸入樣例 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; }

?

轉載于:https://www.cnblogs.com/bxd123/p/10502517.html

總結

以上是生活随笔為你收集整理的【noip模拟赛1】古韵之鹊桥相会（最短路）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。