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

分析與題解

本著暴力出奇跡的原則，先用暴力法的思想考慮了一通， 發(fā)現(xiàn)用暴力法完全沒辦法判斷格子的連通性， 于是轉(zhuǎn)向DFS解法。

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

那么如何檢測T型剪紙呢？
我們可以通過循環(huán)暴力求解出剪出5個格子的所有方案， 對每個方案進(jìn)行連通性檢測(類似迷宮)， 若連通，則累加， 最后輸出累加結(jié)果。

注意：在設(shè)定mp數(shù)組時，將{1,2,3,4,5,6,7,8,9,10,11,12}改為{1,2,3,4, 6,7,8,9, 11,12,13,14} 即可輕松判斷某一格子是否在其兩側(cè)或上下

最后貼上代碼，代碼中有詳細(xì)的注釋。

---

代碼展示

#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; //結(jié)果 int b[4] = {-1, 1, -5, +5}; //通過b數(shù)組檢測是否有格子連通 void dfs(int n) { //檢測連通性 for(int i = 0; i < 4; i++) { //遍歷b數(shù)組，檢測格子的聯(lián)通性 int t = aa[n] + b[i]; //用t存儲 if(t<1 || t>14 || t==5 || t==10) continue;//t值不規(guī)范，結(jié)束本層循環(huán) //從0開始， for(int j = 0; j < 5; j++) //開始檢測五個格子中的每個格子是否與編號為n的格子連通 if(!vis[j] && aa[j]==t) { //若某格子既沒被訪問過，又與編號為n的格子連通 vis[j] = 1; //該格子改為被訪問過 dfs(j); //從該格子開始繼續(xù)向下dfs }} }int main() {ios::sync_with_stdio(false); //加快c++速度 for(int a = 0; a < 12; a++) //五層循環(huán)，尋找任意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; }

---

這世界就是，一些人總在晝夜不停的努力，而另外一些人，起床就發(fā)現(xiàn)世界已經(jīng)變了。

總結(jié)

以上是生活随笔為你收集整理的原理详解与标准解法——蓝桥杯_2016年省赛B组 第七题 剪邮票(暴力+迷宫变形)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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