Question:

Result:? 116

Solve:

這個題意還是比較好懂的，就是12個數里找出5個數，然后看這5個數在方格中的位置是否相連，

代碼也是這個思路，但確實不太好寫，我換了好幾種方案，最后寫成了類似DFS里又套一個DFS的代碼。

首先通過深搜去搞出12選5的全部組合，然后通過再一個DFS去判斷選出的5個數在方格中是不是連通塊

我寫的判斷連通塊的方法是一個最暴力的方法，模擬出方格，然后從選出的第一個數(同時計數為1)開始，判斷其四周有沒有選出的數，如果有，計數加一，并去dfs那個數，在不斷搜索的過程中如果計數到了5，就說明5個數是連在一起的，結果數加一。

上代碼吧，注釋寫的也比較多。

Code:

#include <bits/stdc++.h> using namespace std;int cnt, res = 0; //res記錄結果 bool vis[4][5]; //標記選出的5個數的坐標 bool vis2[4][5]; //標記5個坐標在dfs過程中是否經過 int dir[4][2] = {1,0,-1,0,0,1,0,-1}; //四個方向 //判斷是不是連通塊 void dfs(int x, int y) {//是連通塊，結果加一 if(cnt == 5) res++;for(int i = 0; i < 4; i++){int dx = x + dir[i][0];int dy = y + dir[i][1];//邊界檢測，是否已經走過檢測 if(vis2[dx][dy] || dx < 1 || dy < 1 || dx > 3 || dy > 4) continue;//是否為選中數判斷 if(!vis[dx][dy]) continue;cnt++; vis2[dx][dy] = true;dfs(dx,dy);} }//12選5的全排列 void que(int deep, int num) {if(deep > 5){cnt = 1;memset(vis2,false,sizeof(vis2));//找出第一個選出的數字進入連通塊判斷 for(int i = 1; i <= 3; i++){for(int j = 1; j <= 4; j++){if(vis[i][j]){vis2[i][j] = true;dfs(i,j);//判斷結束后直接返回 return;}}}}//進行全排列，并且將選出的數以坐標的形式標記下來 for(int i = num+1; i <= 12; i++){if(i%4==0){vis[i/4][4] = true;que(deep+1,i);vis[i/4][4] = false;}else{vis[i/4+1][i%4] = true;que(deep+1,i);vis[i/4+1][i%4] = false;}} }int main(void) {memset(vis,false,sizeof(vis));que(1,0);cout <<res;return 0; }

最后附上藍橋杯匯總鏈接：藍橋杯C/C++A組省賽歷年真題題解?

聲明：圖片均來源于藍橋杯官網，以個人刷題整理為目的，如若侵權，請聯系刪除~

總結

以上是生活随笔為你收集整理的蓝桥杯.剪邮票(DFS)的全部內容，希望文章能夠幫你解決所遇到的問題。

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