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

請你計算，一共有多少種不同的剪取方法。

請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。
注意：你提交的應(yīng)該是一個整數(shù)，不要填寫任何多余的內(nèi)容或說明性文字。

思路：一開始準(zhǔn)備建圖跑dfs，但是那樣的話，就會少很多種情況，例如2 5 6 7 10這樣的情況。就只能每層dfs的時候，都要對已經(jīng)走過的格子，進(jìn)行擴(kuò)展。當(dāng)已經(jīng)走過5個格子的時候，將走過的格子數(shù)改成字符串，放到set中，最終set里面字符串的個數(shù)就是答案數(shù)。
代碼如下：

#include<bits/stdc++.h> using namespace std;const int maxx=1e5+100;int vis[3][4],b[5][5]; int tol; int d[4][2]={{-1,0},{1,0},{0,1},{0,-1}}; int a[10]; set<string> s; inline string fcs() {string ans="";string tt;for(int i=0;i<5;i++){int x=a[i];tt="";if(x==0) tt="0";while(x){tt=tt+(char)('0'+x%10);x/=10;}reverse(tt.begin(),tt.end());ans=ans+tt+" ";}//cout<<ans<<endl;return ans; } inline void dfs(int cnt) {if(cnt==5){int tmp=0;for(int i=0;i<3;i++){for(int j=0;j<4;j++){if(vis[i][j]) a[tmp++]=b[i][j];}}//cout<<tmp<<endl;s.insert(fcs());return ;}for(int i=0;i<3;i++){for(int j=0;j<4;j++){if(vis[i][j]){for(int k=0;k<4;k++){int x=d[k][0]+i;int y=d[k][1]+j;if(x<0 || x>=3 || y<0 || y>=4)continue;if(!vis[x][y]){vis[x][y]=1;dfs(cnt+1);vis[x][y]=0;}}}}} } int main() {tol=0;memset(vis,0,sizeof(vis));int num=0;for(int i=0;i<3;i++) for(int j=0;j<4;j++) b[i][j]=++num;for(int i=0;i<3;i++){for(int j=0;j<4;j++){vis[i][j]=1;dfs(1);vis[i][j]=0;}}printf("%d\n",s.size());return 0; }

努力加油a啊

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯2016省赛真题-剪邮票(dfs)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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