[蓝桥杯2016初赛]剪邮票

题目描述

如下图, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）

比如，下面两张图中，粉红色所示部分就是合格的剪取。

image image

请你计算，一共有多少种不同的剪取方法。

输出

请填写表示方案数目的整数。

代码

#include<iostream>
#include<ctime>
#include<cmath>
#include<bits/stdc++.h>
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<<sum;
}