原理詳解與標準解法——藍橋杯_2016年省賽B組 第七題 剪郵票(暴力+迷宮變形)

如【圖1.jpg】, 有12張連在一起的12生肖的郵票。現在你要從中剪下5張來，要求必須是連著的。（僅僅連線一個角不算相連）比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合> 格的剪取。

分析與題解

本著暴力出奇跡的原則，先用暴力法的思想考慮了一通， 發現用暴力法完全沒辦法判斷格子的連通性， 於是轉向DFS解法。

正常考慮：每個格子作為起點，DFS連五張格子，最後去重， 最終得到最後結果。但由於正常情況下DFS沒辦法同時向兩個方向保持探索， 因此無法解決T型剪紙的問題，如

那麼如何檢測T型剪紙呢？
我們可以通過迴圈暴力求解出剪出5個格子的所有方案， 對每個方案進行連通性檢測(類似迷宮)， 若連通，則累加， 最後輸出累加結果。

注意：在設定mp陣列時，將{1,2,3,4,5,6,7,8,9,10,11,12}改為{1,2,3,4, 6,7,8,9, 11,12,13,14} 即可輕鬆判斷某一格子是否在其兩側或上下

最後貼上程式碼，程式碼中有詳細的註釋。

---

程式碼展示

#include<iostream>
#include<algorithm>
using namespace std;
int mp[12] = {1,2,3,4, 6,7,8,9, 11,12,13,14};	 
int aa[5];			//五個格子的編號 
int vis[5];			//每個格子是否被存取過 
int sum = 0;		//結果 
int b[4] = {-1, 1, -5, +5};		//通過b陣列檢測是否有格子連通 

void dfs(int n) {		//檢測連通性 
	for(int i = 0; i < 4; i++) {	//遍歷b陣列，檢測格子的聯通性 
		int t = aa[n] + b[i];		//用t儲存 
		if(t<1 || t>14 || t==5 || t==10) continue;//t值不規範，結束本層迴圈 
		
		//從0開始， 
		for(int j = 0; j < 5; j++) 	//開始檢測五個格子中的每個格子是否與編號為n的格子連通 
			if(!vis[j] && aa[j]==t) {	//若某格子既沒被存取過，又與編號為n的格子連通 
				vis[j] = 1;			//該格子改為被存取過 
				dfs(j);				//從該格子開始繼續向下dfs 
			}
	}
}


int main() {
	ios::sync_with_stdio(false);	//加快c++速度 
	for(int a = 0; a < 12; a++) 	//五層迴圈，尋找任意5格子。 
	for(int b = a+1; b < 12; b++)
	for(int c = b+1; c < 12; c++) 
	for(int d = c+1; d < 12; d++)
	for(int e = d+1; e < 12; e++) {	
		aa[0]=mp[a]; aa[1]=mp[b]; aa[2]=mp[c]; aa[3]=mp[d]; aa[4]=mp[e];	//賦值 
		
		for(int i = 0; i < 5; i++) vis[i] = 0;	//每次判斷前先初始化 
		
		vis[0] = 1;		//從第一個格子開始，因此第一個格子一定被存取過 
		dfs(0); 		//從0開始回溯 
		int flag = 1;
		for(int i = 0; i < 5; i++) 	//最後判斷5個格子是否都被存取過，若是，則連通。 
			if(vis[i] != 1) {
				flag = 0; break;
			}
		if(flag == 0) continue;
		else sum++;
	} 
	cout << sum << endl;
return 0; }

---

這世界就是，一些人總在晝夜不停的努力，而另外一些人，起床就發現世界已經變了。