2020-10-13

剪邮票

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

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

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

题解

#include <iostream>
#include <vector>
#include<algorithm>
#include<map>
using namespace std;

int a[12]={0,0,0,0,0,0,0,1,1,1,1,1}; 
int b[3][4];
int cnt=0;

void dfs(int i,int j){
    b[i][j]=0;//上下左右 
	if(i-1>=0&&i-1<3&&b[i-1][j]==1) dfs(i-1,j);
	if(i+1>=0&&i+1<3&&b[i+1][j]==1) dfs(i+1,j);
	if(j-1>=0&&j-1<4&&b[i][j-1]==1) dfs(i,j-1);
	if(j+1>=0&&j+1<4&&b[i][j+1]==1) dfs(i,j+1);
}

bool check(){
	for(int i=0;i<3;i++){
		for(int j=0;j<4;j++){
			if(a[i*4+j]==1) b[i][j]=1;
			else b[i][j]=0;
		} 
    }    
    int sum=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<4;j++){
			if(b[i][j]==1){
				dfs(i,j);
				sum++;
			}  	
		}
	}
    return sum==1;
}

int main(){
	do{
	   if(check()) cnt++;
	}while(next_permutation(a,a+12)); 
	cout<<cnt<<endl;
	return 0;
}

#深搜部分理解有难度