七段碼
小藍要用七段碼數位管來表示一種特殊的文字。
上圖給出了七段碼數位管的一個圖示，數位管中一共有 7 段可以發光的二極管，分别标記為 a, b, c, d, e, f, g。
小藍要選擇一部分二極管（至少要有一個）發光來表達字元。在設計字元的表達時，要求所有發光的二極管是連成一片的。
- 例如：b 發光，其他二極管不發光可以用來表達一種字元。
- 例如：c 發光，其他二極管不發光可以用來表達一種字元。
這種方案與上一行的方案可以用來表示不同的字元，盡管看上去比較相似。
- 例如：a, b, c, d, e 發光，f, g 不發光可以用來表達一種字元。
- 例如：b, f 發光，其他二極管不發光則不能用來表達一種字元，因為發光的二極管沒有連成一片。
請問，小藍可以用七段碼數位管表達多少種不同的字元？
答案
80
思路
考場上腦抽了，這一看就是圖的題，就想着用Map + List建圖，折騰了半個小時，發現這是無向圖，然後絕望了，在草稿紙上推了一下，亂填了個60…
後面發現其實很簡單，暴力就完了，填空題不求算法有多麼好，隻要能得到正确答案就行。雖然參加的是Java組的，但後面敲的是C++的解析，湊合着看吧~差不多的。吐槽考場辣雞Eclipse瘋狂報錯，提供的是JDK1.8卻隻能用JDK1.4編譯氣死了。
吐槽完了，說一下下面代碼的思路：
- 首先初始化建圖（鄰接表有點麻煩，鄰接矩陣真香！）
- 爆搜路徑長度1 - 7的所有對應的圖的路徑
- 檢查路徑是不是連通的（DFS、并查集都可）
- 輸出滿足條件的路徑個數
===== 21.02.19 update 并查集 =====
DFS + 并查集
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
using std::string;
using std::vector;
// 七段碼所有亮燈情況的存儲容器
vector<string> candidate;
// 鄰接矩陣存儲，真香
int graph[7][7];
// 基礎并查集
struct DisjointSet {
int* father;
explicit DisjointSet(int n) {
father = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
// 找爸爸
int findRoot(int x) {
return father[x] == x ? x : father[x] = findRoot(father[x]);
}
// 合并
bool merge(int x, int y) {
int root_x = findRoot(x);
int root_y = findRoot(y);
if (root_x != root_y) {
father[root_x] = root_y;
}
return root_x != root_y;
}
};
/**
* 鄰接矩陣初始化，1 代表連通
*/
void init() {
// a : 0, b : 1, c : 2
// d : 3, e : 4, f : 5, g : 6
memset(graph, 0, sizeof(graph));
// connect with 'a'
graph[0][1] = graph[0][5] = 1;
// connect with 'b'
graph[1][0] = graph[1][2] = graph[1][6] = 1;
// connect with 'c'
graph[2][1] = graph[2][3] = graph[2][6] = 1;
// connect with 'd'
graph[3][1] = graph[3][4] = 1;
// connect with 'e'
graph[4][3] = graph[4][5] = graph[4][6] = 1;
// connect with 'f'
graph[5][0] = graph[5][4] = graph[5][6] = 1;
// connect with 'g'
graph[6][1] = graph[6][2] = graph[6][4] = graph[6][5] = 1;
}
/**
* 爆搜亮燈的所有情況，換句話說：是要找出 "abcdefg" 中
* 你所需要全排列。非常經典的題了，推薦去 Bilibili 搜尋 BV1qE411E7di
* 并把這位 UP 主的 dfs系列視訊看完，去做對應的練習，你也能很快學會！
* @param result 搜尋到的答案
* @param end 搜尋邊界條件
* @param index 目前搜尋的開始位置
*/
void dfs(string& result, int end, int index) {
if (result.length() == end) {
candidate.emplace_back(result);
return;
}
for (int i = index; i < 7; i++) {
result.push_back('a' + i);
dfs(result, end, i + 1);
result.pop_back();
}
}
/**
* 使用并查集去檢查每一種情況是否符合題目條件
* 即判斷這個字元串對應的圖是否是連通圖
* 一開始，我也不太了解這道題為啥可以用并查集做
* 想了一會，回想起寫 dfs 判斷圖連通的“痛苦回憶”
* 啊，原來并查集在這裡隻是用來輔助我們檢查圖是否連通的啊
* 那沒事了，暴力就完了
*/
void process() {
int ans = 0;
// 周遊每一種候選情況
for (auto str : candidate) {
// 初始化并查集
DisjointSet disj{ 7 };
int len = str.length();
// 這個雙重暴力就不用解釋了吧~
// 用來檢查 str[i] 和 str[j] 對應的點是否是連通的
// 如果連通，我們就把它們合并
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (graph[str[i] - 'a'][str[j] - 'a']) {
disj.merge(str[i] - 'a', str[j] - 'a');
}
}
}
// 如果這個圖是連通圖，那麼對應這張圖的所有點
// 将隻會存在一個點是 disj.father[ch - 'a'] == ch - 'a'
// 即隻有一個點是初始值狀态，若不是，則表示這張圖不連通
int cnt = 0;
for (auto ch : str) {
if (disj.father[ch - 'a'] == ch - 'a') {
cnt++;
}
}
if (cnt == 1) {
ans++;
}
}
printf("%d\n", ans);
}
int main() {
string result;
init();
// 全排列長度 1 - 7 的所有情況~
// eg :
// len = 1 -> "a" "b" "c" "d" "e" "f" "g"
// len = 2 -> "ac" "ad" "ae" "ag" "bd" "be"...
for (int i = 1; i <= 7; i++) {
dfs(result, i, 0);
}
process();
// hhh, 是不是要比 DFS 檢查圖聯通要簡潔呢?
return 0;
}
雙重DFS
// 數字燈管
// 暴力枚舉 + dfs 判斷圖連通
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <unordered_set>
using std::unordered_set;
using std::string;
using std::vector;
vector<char> graph[7];
bool used[7];
void initGraph() {
// connect with 'a'
graph[0].push_back('b');
graph[0].push_back('f');
// connect with 'b'
graph[1].push_back('a');
graph[1].push_back('c');
graph[1].push_back('g');
// connect with 'c'
graph[2].push_back('b');
graph[2].push_back('d');
graph[2].push_back('g');
// connect with 'd'
graph[3].push_back('c');
graph[3].push_back('e');
// connect with 'e'
graph[4].push_back('d');
graph[4].push_back('f');
graph[4].push_back('g');
// connect with 'f'
graph[5].push_back('a');
graph[5].push_back('e');
graph[5].push_back('g');
// connect with 'g'
graph[6].push_back('b');
graph[6].push_back('c');
graph[6].push_back('e');
graph[6].push_back('f');
}
void dfs(vector<string>& ans, string& way, int len, int index) {
if (way.size() == len) {
ans.emplace_back(way);
return;
}
for (int i = index; i < 7; i++) {
way.push_back('a' + i);
dfs(ans, way, len, i + 1);
way.pop_back();
}
}
void isConnected(unordered_set<char>& way, bool& flag, char vertex, int& cnt, int len) {
if (cnt == len) {
flag = true;
return;
}
for (auto ch : graph[vertex - 'a']) {
if (!used[ch - 'a'] && way.count(ch)) {
used[ch - 'a'] = true;
cnt++;
isConnected(way, flag, ch, cnt, len);
}
}
}
int main() {
initGraph();
vector<string> ans_maybe;
string way;
for (int i = 1; i <= 7; i++) {
dfs(ans_maybe, way, i, 0);
}
int cnt = 0;
unordered_set<char> us;
unordered_set<string> notAns;
for (auto& way : ans_maybe) {
memset(used, 0, sizeof(used));
for (auto ch : way) {
us.insert(ch);
}
bool flag = false;
int vertexes = 1;
used[way[0] - 'a'] = true;
isConnected(us, flag, way[0], vertexes, way.length());
if (flag) {
cnt++;
notAns.insert(way);
}
us.clear();
}
printf("%d\n", cnt);
for (auto& s : ans_maybe) {
if (!notAns.count(s)) {
printf("%s\n", s.c_str());
}
}
return 0;
}