12.七段碼 - 藍橋云課

將七個二極管映射為 1-7?

開一個二維矩陣 為 相鄰的邊連上線?

edge[1][2] = edge[1][6] = 1;edge[2][1] = edge[2][3] = edge[2][7] = 1;edge[3][2] = edge[3][4] = edge[3][7] = 1;edge[4][3] = edge[4][5] = 1;edge[5][4] = edge[5][6] = edge[5][7] = 1;edge[6][1] = edge[6][5] = edge[6][7] = 1;edge[7][2] = edge[7][3] = edge[7][5] = edge[7][6] = 1;

由于數據量比較小 一共也就? ? 2^7 = 128種狀態 直接搜索枚舉每個二極管亮還是滅?

將連在一起的邊視為連通塊 遞歸到最后一層 判斷的時候 查看 亮著的聯通塊是否大于1 如果等于1則方案數+1?

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int edge[10][10];
int p[10];
bool st[10];
int ans = 0;
int find(int x){if(p[x] != x){p[x] = find(p[x]);//路徑壓縮 }return p[x];//找到根節點了 直接返回  
}
void dfs(int u){if(u==8){for(int i = 1 ;i<=7;i++){p[i] = i ; // 初始化 自己指向自己作為根節點 }for(int i = 1 ;i <8;i++){for(int j = 1 ; j<8;j++){if(edge[i][j] && st[i]&&st[j] ){///如果兩者相鄰并且都亮著 合并為一個聯通塊  p[find(i)] = find(j);//指向同一個根節點 }}}	int cnt = 0 ;for(int i = 1;i<8;i++){if(st[i]&&(p[i] == i)){cnt++;}}if(cnt==1){ans++;}return ;}st[u] = 1;//第u個二極管亮 dfs(u+1);// 遞歸下個管 st[u] = 0;回溯   第u個二極管滅 dfs(u+1);}
int main(){edge[1][2] = edge[1][6] = 1;edge[2][1] = edge[2][3] = edge[2][7] = 1;edge[3][2] = edge[3][4] = edge[3][7] = 1;edge[4][3] = edge[4][5] = 1;edge[5][4] = edge[5][6] = edge[5][7] = 1;edge[6][1] = edge[6][5] = edge[6][7] = 1;edge[7][2] = edge[7][3] = edge[7][5] = edge[7][6] = 1;dfs(1);cout<<ans;return 0;
}