| 【第二十一题】成语接龙（北理工/北京理工大学/程序设计方法与实践/小学期 ） | 您所在的位置：网站首页 › 华为p20pro怎么拿出手机卡 › 【第二十一题】成语接龙（北理工/北京理工大学/程序设计方法与实践/小学期 ） |
【第二十一题】成语接龙（北理工/北京理工大学/程序设计方法与实践/小学期 ）
|
目录 前言 参考资料 思路 初始代码 修复代码 前言这道题是典型的bfs，但是需要自己构建图，所以难度高一点。 参考资料首先学一下图相关的知识，图的定义，两种表示方式，两种搜索算法BFS和DFS： 图的详解_Lin-Cheng的博客-CSDN博客 还有就是map，queue，vector的概念和用法，上csdn搜一搜即可 思路
用map和vector结合起来构造邻接链表形式的图结构。 具体说就是，用map下标为成语的末尾，与这个下标对应的vector储存了以这个末尾为开头的所有成语的末尾。 有了图以后就是经典的bfs环节了。 初始代码wa了2发，原因初步猜测是系统错误，当时这么做的时候心理就有点不安，事实证明，可能发生的事情，在足够的数据量面前，必然发生。 #include #include #include #include #include #define SIZE 1000010 //单纯用结尾当下标的合理性： int step[SIZE]; bool vis[SIZE]; int main(void) { // freopen("input.txt", "r", stdin); int i, m, temp1, temp2, s1, s2, s3, s4, e1, e2, e3, e4; std::map gragh; std::queue q; //读入所有给出成语的头尾，构造图；读入开始成语和结束成语的全部 scanf("%d", &m); scanf("%*d %*d %*d %*d");//清除掉第一个单词防止干扰 for (i = 1; i < m; i++) { scanf("%d %*d %*d %d", &temp1, &temp2); gragh[temp1].push_back(temp2); } scanf("%d %d %d %d", &s1, &s2, &s3, &s4); scanf("%d %d %d %d", &e1, &e2, &e3, &e4); //判断是否自环 if (s1 == e1 && s2 == e2 && s3 == e3 && s4 == e4) { printf("1\n");//自环就直接输出 return 0; } else //不是自环就bfs { memset(step, -1, sizeof step); memset(vis, false, sizeof vis); q.push(s4); vis[s4] = true; step[s4] = 1; while (!q.empty()) { //出队,第一个top应该是s4 int top = q.front(); q.pop(); //打入top的下一层 for (auto x : gragh[top])//遍历vector, { if (!vis[x]) { q.push(x); vis[x] = true; //增加访问标记 step[x] = step[top] + 1; //走到x的步数是走到top的步数的下一步 if (x == e4) break; //因为是一层一层的，所以一旦发现了，就必然最优 } } } printf("%d\n", step[e4]); return 0; } } 修复代码激动的心，颤抖的手！ AC啦！ 意料之外，情理之中。 之前的代码有个系统错误： 为了节省空间，使用了一维数组去存是否被访问过得状态，但是下标是结尾，开头不管了吗？ 如果不顾开头，就会出现提前找到假结尾的情况，比如： 6 1 2 3 4 4 6 7 10 4 5 6 7 7 8 9 10 4 6 6 1 1 6 8 8 1 2 3 4 7 8 9 10 正常应该是1234 4567 789 10 但是有个 467 10，就会提前找到，输出2，所以要加一个同时判断开头和结尾的判断，这样才会输出3. if (top == e1 && x == e4) break;但是这里又会出现一种情况，我是找到了假结尾，我们是不break，但是给人家结尾代表的visit和step影响了，以后碰到真结尾，因为已经访问过了，所以就跳过了，所以假结尾还要再增加修复。 if (top != e1 && x == e4) { vis[x] = false; step[x]--; }做到以上两点，就彻底解决了用一维数组带来的影响。 #include #include #include #include #include #define SIZE 1000010 //单纯用结尾当下标的合理性：如果不加任何措施，可能会出现，不同开头，相同结尾的节点发生干扰的情况 int step[SIZE]; bool vis[SIZE]; int main(void) { freopen("input.txt", "r", stdin); int i, m, temp1, temp2, s1, s2, s3, s4, e1, e2, e3, e4; std::map gragh; std::queue q; //读入所有给出成语的头尾，构造图；读入开始成语和结束成语的全部 scanf("%d", &m); for (i = 0; i < m; i++) { scanf("%d %*d %*d %d", &temp1, &temp2); gragh[temp1].push_back(temp2); } scanf("%d %d %d %d", &s1, &s2, &s3, &s4); scanf("%d %d %d %d", &e1, &e2, &e3, &e4); //判断是否自环 if (s1 == e1 && s2 == e2 && s3 == e3 && s4 == e4) { printf("1\n");//自环就直接输出 return 0; } else //不是自环就bfs { memset(step, -1, sizeof step); memset(vis, false, sizeof vis); q.push(s4); vis[s4] = true; step[s4] = 1; while (!q.empty()) { //出队,第一个top应该是s4 int top = q.front(); q.pop(); //打入top的下一层 for (auto x : gragh[top])//遍历vector, { if (!vis[x]) { q.push(x); vis[x] = true; //增加访问标记 step[x] = step[top] + 1; //走到x的步数是走到top的步数的下一步 if (top != e1 && x == e4)//修复假结尾的影响 { vis[x] = false; step[x]--; } if (top == e1 && x == e4) //因为是一层一层的，所以一旦发现了，就必然最优 break; } } } printf("%d\n", step[e4]); return 0; } } |
【本文地址】
公司简介
联系我们