題目描述
如下圖, 有12張連在一起的12生肖的郵票。現在你要從中剪下5張來，要求必須是連着的。(僅僅連接配接一個角不算相連)
比如，下面兩張圖中，粉紅色所示部分就是合格的剪取。
image
image
請你計算，一共有多少種不同的剪取方法。
輸出
請填寫表示方案數目的整數。
代碼
#include
#include
#include
#include
using namespace std;
int sum=0;
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int visit[3][4];
int has[100010];
//每個方格看成二進制的一個位，然後比較所有位算出的十進制的數字是否一樣
void dfs(int n){
if(n==5){
int temp=0;
for(int i=0;i<3;i++){
for(int j=0;j<4;j++){
temp+=visit[i][j];
temp<<=1;
}
}
if(!has[temp]){
sum++;
has[temp]=1;
}
return;
}
for(int i=0;i<3;i++){
for(int j=0;j<4;j++){
if(visit[i][j]){
for(int k=0;k<4;k++){
int xx=i+dir[k][0];
int yy=j+dir[k][1];
if(!visit[xx][yy]&&xx<3&&yy<4&&xx>=0&&yy>=0){
visit[xx][yy]=1;
dfs(n+1);
visit[xx][yy]=0;
}
}
}
}
}
}
int main()
{
for(int i=0;i<3;i++){
for(int j=0;j<4;j++){
visit[i][j]=1;
dfs(1);
visit[i][j]=0;
}
}
cout<
}