dfs + 手动判断连通（参考别的同学的）

题目描述

七段码

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[10];
int cnt;
bool check(){
    int k=0;
    for(int i=1;i<=7;i++){
        if(a[i]==1) k++;
    }
    if(k==0)return false;
    if(k==1)return true;
    // 每根管子连接情况 
    if(a[1]==1){
        if(a[2]!=1 && a[6] !=1) return false;
    }
    if(a[2]==1){
        if(a[1]!=1 && a[3]!=1 && a[7]!=1) return false;
    }
    if(a[3]==1){
        if(a[2]!=1 &&a[4]!=1 && a[7]!=1) return false;
    }
    if(a[4]==1){
        if(a[3]!=1 && a[5]!=1) return false;
    }
    if(a[5]==1){
        if(a[4]!=1 && a[6]!=1 && a[7]!=1) return false;
    }
    if(a[6]==1){
        if(a[1]!=1 && a[5]!=1 && a[7]!=1) return false;
    }
    if(a[7]==1){
        if(a[2]!=1 && a[3]!=1 && a[5]!=1 && a[6]!=1) return false;
    }
    return true;
}
void dfs(int k){
    if(k==8){
//      for(int i=1;i<=7;i++) cout<<a[i]<<" ";
//      cout<<endl;
        if(check()) cnt++;
        return;
    }
    a[k]=1;
    dfs(k+1);
    a[k]=0;
    dfs(k+1);
    return;
}
int main(){
    dfs(1);
    cout<<cnt-3;
}