題意：
? ? ? 給你一個n*m的矩陣，上面只有兩種字符，X或者O，每次可以同時改變相同顏色的一個連通塊，上下左右連通才算連通，用最小的步數把這個圖弄成全是X或者全是O，題意要是沒看懂看下面的樣例。
Sample Input

2
2 2
OX
OX
3 3
XOX
OXO
XOX
Sample Output

1
2
Hint
For the second sample, one optimal solution is:
Step 1. flip (2, 2)

XOX
OOO
XOX
Step 2. flip (1, 2)

XXX
XXX
XXX

思路：
? ? ? 這個可以用最短路來做（也可以直接廣搜，因為是在格子上找距離），首先我們要把每一個連通塊縮成一個點，然后把相鄰的聯通快之間建邊，然后枚舉每一個點為起點，跑單源最短路，然后對于每一個點的當前答案就是所有點中離他最遠的那個，最后在在每一個最遠的點鐘找到最小的那個，為什么這么做是對的，我們就假設我們枚舉的最短路的起點是中心點，我們從中心點往外擴，每一次絕對可以擴展一層，這

一層有兩種擴展方式，改變中間或者改變要擴展的這層，畫一下就理解了。。

#include<stdio.h> #include<string.h> #include<queue> #include<map>#define N_node 1600 + 100 #define N_edge 2000000 #define INF 100000000using namespace std;typedef struct {int to ,next ,cost; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int s_x[N_node]; int mapp[50][50] ,n ,m; int mk[50][50]; int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0}; map<int ,map<int ,int> >kk;void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }int spfa(int s ,int n) {for(int i = 0 ;i <= n ;i ++)s_x[i] = INF;int mark[N_node] = {0};mark[s] = 1;s_x[s] = 0;queue<int>q;q.push(s);while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost){s_x[xin] = s_x[tou] + E[k].cost;if(!mark[xin]) {mark[xin] = 1;q.push(xin);}}}}int now = 0;for(int i = 1 ;i <= n ;i ++)if(now < s_x[i]) now = s_x[i];return now; }bool ok(int x ,int y ,int ys) {return x >= 1 && x <= n && y >= 1 && y <= m && !mk[x][y] && mapp[x][y] == ys;} void DFS(int x ,int y ,int now ,int ys) {for(int i = 0 ;i < 4 ;i ++){int xx = x + dir[i][0];int yy = y + dir[i][1];if(ok(xx ,yy ,ys)){mk[xx][yy] = now;DFS(xx ,yy ,now ,ys);}}return ; }int main () {int i ,j ,t;char str[50];scanf("%d" ,&t);while(t --){scanf("%d %d" ,&n ,&m);for(i = 1 ;i <= n ;i ++){scanf("%s" ,str);for(j = 1 ;j <= m ;j ++)mapp[i][j] = str[j-1] == 'X';}memset(mk ,0 ,sizeof(mk));int now = 0;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++){if(mk[i][j]) continue;mk[i][j] = ++now;DFS(i ,j ,now ,mapp[i][j]);}kk.clear();memset(list ,0 ,sizeof(list)) ,tot = 1;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++){if(i > 1){if(mk[i][j] != mk[i-1][j] && !kk[mk[i][j]][mk[i-1][j]]){kk[mk[i][j]][mk[i-1][j]] = 1;add(mk[i][j] ,mk[i-1][j] ,1);}}if(i < n){if(mk[i][j] != mk[i+1][j] && !kk[mk[i][j]][mk[i+1][j]]){kk[mk[i][j]][mk[i+1][j]] = 1;add(mk[i][j] ,mk[i+1][j] ,1);}}if(j > 1){if(mk[i][j] != mk[i][j-1] && !kk[mk[i][j]][mk[i][j-1]]){kk[mk[i][j]][mk[i][j-1]] = 1;add(mk[i][j] ,mk[i][j-1] ,1);}}if(j < m){if(mk[i][j] != mk[i][j+1] && !kk[mk[i][j]][mk[i][j+1]]){kk[mk[i][j]][mk[i][j+1]] = 1;add(mk[i][j] ,mk[i][j+1] ,1);}}}int ans = INF;for(i = 1 ;i <= now ;i ++){int tmp = spfa(i ,now);if(ans > tmp) ans = tmp;}printf("%d\n" ,ans);}return 0; }

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的ZOJ 3781 最短路（想法好题目）的全部內容，希望文章能夠幫你解決所遇到的問題。

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