BFS深度优先算法 ``` #include <cstdio> int g[7][7]={ {1,1,0,0,0,1,0}, {1,1,1,0,0,0,1}, {0,1,1,1,0,0,1}, {0,0,1,1,1,0,0}, {0,0,0,1,1,1,1}, {1,0,0,0,1,1,1}, {0,1,1,0,1,1,1} }; bool vis[7]; int dfs(int a){ int cnt =1; for(int i =0;i<7;i++){ if(!vis[i]&&g[a][i]){ vis[i]=true; cnt+=dfs(i); vis[i]=false; } } return cnt; } int main(){ printf("%d\n",dfs(0)/2); return 0; } ``` g[7][7]数组代表了七段码数码管中各个二极管之间的连接关系。在这个数组中，1表示两个二极管是相邻的，可以一起发光来表示一个字符；0则表示它们不是相邻的。 具体来说，这个二维数组的每一行和每一列都代表了一个二极管，数组中的每个元素g[i][j]代表了二极管i和二极管j是否相邻。如果g[i][j]为1，那么二极管i和j是相邻的；如果为0，则不相邻。 例如，g[0][1]是1，表示二极管a和b是相邻的。而g[0][2]是0，表示二极管a和c不是相邻的。 逐步分析dfs函数： 1. int cnt = 1;：这行代码初始化了一个名为cnt的计数器，用于记录从当前二极管开始，连续发光的二极管数量。初始值为1，因为至少当前二极管是发光的。 2. for(int i = 0; i < 7; i++) { ... }：这个循环遍历所有的二极管，索引从0到6。 3. if(!vis[i] && g[a][i]) { ... }：这个条件判断两件事： !vis[i]：检查二极管i是否没有被访问过。如果vis[i]为false，表示它还没有被访问。 g[a][i]：检查当前二极管a和二极管i是否相邻。如果g[a][i]为1，表示它们是相邻的。 4. vis[i] = true;：这行代码将二极管i标记为已访问。 5. cnt += dfs(i);：这行代码递归调用dfs函数，从二极管i开始继续搜索，并将返回的连续发光二极管数量加到cnt上。 6. vis[i] = false;：这行代码在递归调用返回后，将二极管i的访问状态重置。这样做是为了在后续的搜索中，其他路径也可以访问到这个二极管。 最后结果需要除以2是因为： 在深度优先搜索（DFS）过程中，每个连接的二极管对会被计算两次。这是因为在无向图中，每条边都有两个方向，所以在搜索过程中，每个连接会从两个方向各被探索一次。 例如，如果二极管a和b是相连的，那么在DFS搜索中，我们会从a到b探索一次，然后从b到a再探索一次。这就导致了每个连接被计算了两次。

好难, 可以看看这题: 题目详情 - 剪邮票(结果填空) - DashOJ (算是简单版本?) ```cpp #include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; /* pl 数组 对应 的内容: -0- 1-2 -3- 4-5 -6- */ int main() { // 生成所有可能的全排列, 但是我们只需要符合条件的 int pl[7] = {0}; function<bool(int)> fun = [&](int i) { // 判断这个方案是否合法 // i 是当前点亮的数量 if (i == 1) return true; // 保证是连在一起亮的 if (pl[0] && !(pl[1] || pl[2])) return false; if (pl[1] && !(pl[0] || pl[3] || pl[4])) return false; if (pl[2] && !(pl[0] || pl[3] || pl[5])) return false; if (pl[3] && !(pl[1] || pl[2] || pl[4] || pl[5])) return false; if (pl[4] && !(pl[1] || pl[3] || pl[6])) return false; if (pl[5] && !(pl[2] || pl[3] || pl[6])) return false; if (pl[6] && !(pl[4] || pl[5])) return false; // 保证是单个连通的 // 实际上就剩下3种情况: [fe, bc] , [af, cd], [ab, ed] // 这个是符合上面条件但是没有连通的 (如果写dfs判断的话我不会(太麻烦了)) // 暂时这样吧, 答案 - 3 即可 return true; }; int res = 0; for (int i = 0; i < 7; ++i) { for (int j = 0; j < 7; ++j) { if (j <= i) pl[j] = 1; else pl[j] = 0; cout << pl[j] << ' '; } cout << '\n'; sort(pl, pl + 7); do { if (fun(i + 1)) { ++res; } } while (next_permutation(pl, pl + 7)); } cout << res - 3; // 为什么减? 看上面 return 0; } ```