“多少种”是搜索和dp的关键字

“多少种”是搜索和dp的关键字

题目：七段码

本题求的是方案数，要本能的想到搜索和dp以及二进制枚举
又因为最后还要判断是否联通，有后效性，所以不能所以dp
（同等情况下，代码越长，实现的功能就越多）（dp只能求出总方案数，无法将所有状态保存，最后用来判断是否联通）
所以选用搜索，至于二进制枚举（还不太熟练）

#include<bits/stdc++.h>
using namespace std;
int cnt;
int e[12][12],turn[10],f[10];
void init(){
    e[1][2]=1;e[1][6]=1;
    e[2][1]=1;e[2][3]=1;e[2][7]=1;
    e[3][2]=1;e[3][4]=1;e[3][7]=1;
    e[4][3]=1;e[4][5]=1;
    e[6][5]=1;e[6][1]=1;e[6][7]=1;
    e[7][6]=e[7][5]=e[7][3]=e[7][2]=1;
}
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
    f[find(x)]=find(y);
}
int pan(){
    for(int i=1;i<=7;++i) f[i]=i;
    for(int i=1;i<=7;++i){
        for(int j=1;j<=7;++j){
            if(e[i][j]&&turn[i]&&turn[j]){
                if(find(i)!=find(j)) merge(i,j);
            }
        }
    } 
    int z=0;
    for(int i=1;i<=7;++i){
        if(turn[i]&&find(i)==i) z++;
    }
    return z==1;
}
void dfs(int x){
    if(x>=8) {
        if(pan()) cnt++;
        return ;
    }
    turn[x]=1;
    dfs(x+1);
    turn[x]=0;
    dfs(x+1);
}
int main(){
    init();
    dfs(1);
    cout << cnt;
    return 0;
}