題目描述

七段碼 - 藍(lán)橋云課 (lanqiao.cn)

題目分析?

所有的情況我們可以分析出來一共有2的7次方-1種，因?yàn)槊恳粋€(gè)二極管都有選擇和不選擇兩種情況，有7個(gè)二極管，但是還有一種都不選的情況需要排除，故-1

枚舉每個(gè)方案看是否符合要求，對于每種方案，從任何一個(gè)選中的頂點(diǎn)出發(fā)進(jìn)行dfs，如果這個(gè)方案找到的頂點(diǎn)是亮的并且有邊相連那么這個(gè)方案就符合要求

?是否有邊相連我們使用鄰接矩陣存儲，如第一行，與a相連的邊有b,?f所以g[a][b] = 1, g[a][f] = 1

答案：80

#include<bits/stdc++.h>
using namespace std;
int bright[7];
bool vis[7];
int g[7][7] = 
{{0, 1, 0, 0, 0, 1, 0},{1, 0, 1, 0, 0, 0, 1},{0, 1, 0, 1, 0, 0, 1},{0, 0, 1, 0, 1, 0, 0},{0, 0, 0, 1, 0, 1, 1},{1, 0, 0, 0, 1, 0, 1},{0, 1, 1, 0, 1, 1, 0}
};
void dfs(int x)
{for(int i = 0; i < 7; i ++){if(g[x][i] && bright[i] && !vis[i]){vis[i] = 1;dfs(i);}}
}
int main()
{int ans = 127;//128 - 1for(int i = 1; i <= 127; i ++){memset(vis, 0, sizeof vis);memset(bright, 0, sizeof bright);int x = i;int j = 0;while(x){if(x & 1)bright[j] = 1;x >>= 1;j ++;}int stick = 0;while(!bright[stick])stick ++;vis[stick] = 1;dfs(stick);for(int j = 0; j < 7; j ++){if(bright[j] && !vis[j])//此處應(yīng)該為亮但是卻沒有訪問過說明不相連 {ans --;break;}}}cout << ans; return 0;
}