七段码(蓝桥B组E)

作者： 作者的头像   冷丁Hacker ,  2020-10-17 19:06:21 ,  所有人可见 ,  阅读 691

1 


#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int vis[10];
int a[10];
int b[10];
int ans;
int answer;
int sum;
void bfs2(int cnt) {

    sum++;
    queue<int> q;
    q.push(cnt);
    vis[cnt] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        if (t == 1) {
            if (a[6] == 1&&!vis[6]) {
                q.push(6);
                vis[6] = 1;
            }
            if (a[2] == 1&&!vis[2]) {
                q.push(2);
                vis[2] = 1;
            }
        }
        else if (t == 2) {
            if (a[1] == 1 && !vis[1]) {
                q.push(1);
                vis[1] = 1;
            }
             if (a[3] == 1 && !vis[3]) {
                q.push(3);
                vis[3] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
        }
        else if (t == 3) {
            if (a[2] == 1 && !vis[2]) {
                q.push(2);
                vis[2] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
             if (a[4] == 1 && !vis[4]) {
                q.push(4);
                vis[4] = 1;
            }
        }
        else if (t == 4) {
            if (a[3] == 1 && !vis[3]) {
                q.push(3);
                vis[3] = 1;
            }
             if (a[5] == 1 && !vis[5]) {
                q.push(5);
                vis[5] = 1;
            }
        }
        else if (t == 5) {
            if (a[4] == 1 && !vis[4]) {
                q.push(4);
                vis[4] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
             if (a[6] == 1 && !vis[6]) {
                q.push(6);
                vis[6] = 1;
            }
        }
        else if (t == 6) {
            if (a[5] == 1 && !vis[5]) {
                q.push(5);
                vis[5] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
             if (a[1] == 1 && !vis[1]) {
                q.push(1);
                vis[1] = 1;
            }
        }
        else if (t == 7) {
            if (a[5] == 1 && !vis[5]) {
                q.push(5);
                vis[5] = 1;
            }
             if (a[2] == 1 && !vis[2]) {
                q.push(2);
                vis[2] = 1;
            }
             if (a[3] == 1 && !vis[3]) {
                q.push(3);
                vis[3] = 1;
            }
             if (a[6] == 1 && !vis[6]) {
                q.push(6);
                vis[6] = 1;
            }
        }
    }
    return;

}
void dfs(int num) {

    if (num > 7) {
        ans++;
        sum = 0;
        memset(vis, 0, sizeof(vis));
        memset(b, 0, sizeof(b));
        for (int i = 1; i <= 7; i++) {
            if(a[i]==1&&!vis[i])
                bfs2(i);
        }
        for (int i = 1; i <= 7; i++) {
            cout << a[i];
        }
        cout << ' ';
        cout << sum << endl;
        if (sum == 1) {
            answer++;
            //cout << answer << endl;
        }
        return;
    }
    a[num] = 1;
    dfs(num + 1);
    a[num] = 0;

    a[num] = 0;
    dfs(num + 1);
    a[num] = 1;

    return;
}
int main()
{

    dfs(1);
    cout << answer<< endl;
    return 0;
}

4 评论

用户头像
macat   2020-10-18 07:01      1    踩      回复

用先写出邻接表, 会不会好写一点

#include <iostream>
#include <cstdio>

using namespace std;

int g[8][8] = {//邻接表 
    {1, 5},
    {0, 2, 6},
    {1, 3, 6},
    {2, 4},
    {3, 5, 6},
    {0, 4, 6},
    {1, 2, 4, 5} 
};
int cnt[8] = {2, 3, 3, 2, 3, 3, 4};//邻接表长度 
int st;

void dfs(int u) {
    st -= (1<<u);
    for(int i = 0; i < cnt[u]; ++i) {
        int j = g[u][i];
        if(st>>j&1){
            dfs(j);
        } 
    }
}

int main() {
    int cnt = 0;
    for(int i = 0; i < (1<<7); ++i) {//枚举所有状态 
        for(int j = 0; j < 7; ++j) {//枚举状态中第一个亮的点 
            if(i>>j&1) {
                st = i;
                dfs(j);//深搜寻找连通块，将其位置0 
                //cout<<st<<endl; 
                if(!st) cnt++;//所有均连通合法状态 
                break;  
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}
用户头像
雷军的小迷弟   2023-03-25 16:08         踩      回复

大佬

用户头像
鸽   2020-10-17 19:45         踩      回复

不会做，%%%

用户头像
菜鸡就是我   2020-10-23 18:40         踩      回复

直接数