足球

時間限制: 1 Sec 內存限制: 128 MB

題目描述

yoyo得到了一個足球，這個足球與其他的足球一樣，表面有 12 個正五邊形和 20 個正六邊形組成，足球的每個面初始的時候都為白色。現在yoyo把這個足球拆解開來，32個面編號為1~32。愛畫畫的yoyo希望將足球的某些面涂為黑色（可能是 0 個），在每次涂色操作中，慢慢只可以將某一些相鄰或者聯通的面一起涂為黑色（兩個面相鄰當且僅當他們共用一條邊）。例如，yoyo可以在一次涂色操作中將面 1、2、3、4、5 涂為黑色，但是他不可以將面11 和 24 涂為白色，因為面 11 和 24 是不相鄰也不聯通的。求yoyo所需要的最少的涂色次數。

輸入

第一行包含一個整數 t，表示有t組測試數據，對于每組測試數據：

輸入包含一行，該行包含 32 個整數，每個數的值等于 0 時表示白色，等于 1 時表示黑色。

輸出

對于每組測試數據，輸出Case c: ans，其中 c 為測試數據編號，ans 為最少的操作次數。

樣例輸入

3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

樣例輸入

Case 1: 1 Case 2: 0 Case 3: 2 Case 1: 1 Case 2: 2 Case 3: 2 Case 4: 1 Case 5: 14

提示

除了相鄰的數面也相鄰外，面 1 和面 13 是相鄰的，面 13 和面 17 是相鄰的，面 17 和面 32 是相鄰的，

面 15 和面 32 是相鄰的，面 19 和面 32 是相鄰的。

PS:1和32不相鄰。

題解

先把所有相鄰的點賦值為1，再用Floyd算法把所有點之間的最短距離打表求出來。

之后每輸入一組樣例，則對樣例中的1進行dfs深搜，然后深搜把所有相鄰為1且值為1的點重新賦值為0。

最后記錄下主循環中dfs的次數即可。

#include<bits/stdc++.h> using namespace std; const int maxn = 32 + 1;//最多32個點 int dis[maxn][maxn];//記錄兩點之間的最短距離 int vis[maxn]; void init(){memset(dis,0x3f3f3f3f,sizeof(dis));//初始化dis[32][32] = 0;for(int i = 1; i < maxn - 1; i++){dis[i][i] = 0;//相同兩點的距離為0dis[i][i + 1] = 1;//相鄰兩點之間的距離為1dis[i + 1][i] = 1;//相鄰兩點之間的距離為1}//相鄰兩點之間的距離為1dis[1][13] = dis[13][1] = 1;dis[17][13] = dis[13][17] = 1;dis[17][32] = dis[32][17] = 1;dis[15][32] = dis[32][15] = 1;dis[19][32] = dis[32][19] = 1;//Floyd算法，區間動態規劃for(int k = 1; k < maxn; k++)//枚舉斷點for(int i = 1; i < maxn; i++)for(int j = 1; j < maxn; j++)if(dis[i][j] > dis[i][k]+dis[k][j])dis[i][j] = dis[i][k]+dis[k][j]; }void dfs(int x){vis[x] = 0;//標記已經訪問過for(int i = 1; i < maxn; i++){if(vis[i]&&dis[x][i]==1)dfs(i);} } int main(){init();int t;cin>>t;for(int u = 1;u <= t;u++){for(int i = 1;i < maxn; i++)cin>>vis[i];int ans = 0;for(int i = 1; i < maxn; i++){if(vis[i]){ans++;dfs(i);}}cout<<"Case "<<u<<": "<<ans<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的足球 Floyd算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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