成语接龙 |
您所在的位置：网站首页 › 现在成语接龙 › 成语接龙 |
成语接龙
|
写在最开始：这题能够做出来基本全靠一位学长的经验分享，详见这一篇 --> 【第二十一题】成语接龙（北理工/北京理工大学/程序设计方法与实践/小学期 ）http://t.csdn.cn/fcTLy 这篇真的是小白向。当我上CSDN搜索“图的实现”，出来的结果往往是先梳理图的基本知识，然后立刻就毫无征兆地冒出来一堆莫名其妙的代码，不加任何解释，让我看着非常头大。所以这一篇既是我个人的笔记梳理，也算是帮助其他像我一样没有c++基础的“真”小白入门。 一、题目描述 Description 小张非常喜欢与朋友们玩成语接龙的游戏，但是作为“文化沙漠”的小张，成语的储备量有些不足。现在他的大脑中存储了 m 个成语，成语中的四个汉字都用一个 1e6 以内的正整数来表示。现在小张的同学为了考验他给出了他一个成语做开头和一个成语做结尾，如果小张能通过成语接龙的方式说到结尾的成语，他就能够成功完成游戏。他想知道最少能说几个成语能够成功完成游戏。Input 第一行一个数。 接下来行，每行4个 1e6 以内的正整数，表示一个成语。 下一行4个 1e6 以内的正整数，表示开始成语。 下一行4个 1e6 以内的正整数，表示结束成语。 保证开始成语和结束成语在小张的成语储备之中。 Output 一行一个整数，表示最少说几个成语能够完成游戏。如果无法完成输出-1。Notes 三个成语分别是(1,2,3,4)(4,5,6,7)(7,8,9,10) 测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示 5↵1 2 3 4↵4 5 6 7↵7 8 9 10↵4 6 6 1↵1 6 8 8↵1 2 3 4↵7 8 9 10↵以文本方式显示 3↵1秒64M0二、个人笔记 1、queue和map的简单初始化 queue和map在c++中现成的数据结构，如果会的话可以直接调用，非常方便。 (1) queue queue queue_name;其中，type是数据类型，container是容器类型，queue_name是队列名称。container可以省略。 例如，要初始化一个存储int整型变量、名称为Q的队列： queue Q;(2) map map map_name;其中，type1和type2是两个数据类型，map_name是map名称。 例如，要建一个int类型指向string类型、名为graph的图表： map graph; graph[0] = "abc"; //表示graph中，0指向“abc”2、%*d和%.*d scanf("%d %*d %d",&a,&b); printf("a=%d b=%d\n",a,b); printf("%*d",10,a); printf("\n"); printf("%.*d",10,b);输入 10 20 30 输出 a=10 b=30 10（8个空格，一个10） 0000000030（8个0，一个10） scanf和printf中的%*d是不一样的。 ①scanf中的%*d，会在读入时占用一个数，且不存入变量。 而printf中的%*d，是用空格补齐输出。 ②scanf中的%.*d，是非法的，会报错。 而printf中的%.*d，是用0来补齐输出。 3、queue库的简单操作 Q.push() 在队尾插入一个元素 Q.pop() 删除队列第一个元素 Q.size() 返回队列中元素个数 Q.empty() 如果队列空则返回true Q.front() 返回队列中的第一个元素 Q.back() 返回队列中最后一个元素4、map库的简单操作 插入：graph.insert( pair (type1_data,type2_data) ) 修改：直接修改 graph[0] = "aaa"; 查找：graph.find(key); 删除：graph.erase(key); 清空：graph.clear(); 第一个元素迭代器：graph.begin(); 最后一个元素迭代器：graph.end();当然，这题我只需要用到修改就足够了。 5、auto类型 用来简化变量的初始化，例如： auto i = "Hello world!"; //相当于string i = "Hello world!"; for (auto i=0 ; i7->A。(Ⅱ)代码实现 因为这个题我用的是BFS，所以我先写BFS的代码实现。 //BFS搜索 queue q; bool vis[N] = {false}; //记录点的访问情况。false表示点未被访问，true表示点已经被访问过。 int step[N]; //step表示第N个节点在第几层 //初始化step memset(step,-1,sizeof(step)); //假设起点为s q.push(s); //起点入列 vis[s] = true; //将起点设置为被访问过 step[s] = 1; //起点在第一层 while ( q.size() ) { //只要队列内有元素，就一直执行 //从队列中取出队首 int cur = q.top; q.pop; //下面是伪代码 for (所有和队首相连的边) { int v = 边相连的点; if ( !vis[v] ) { //如果这个点没被访问过 //那么就把这个点加入队列 q.push(v); //并且把这个点设置为被访问过 vis[v] = true; //v的层数是cur的层数+1 step[v] = step[cur] + 1; } } }代码应该是初学者可以看得懂的，没有涉及到什么复杂的知识。 7、一些补充 以上是我的个人笔记，我承认难度不够深，可能一些描述也不够标准。但是对入门来说应该很合适，提前适应一些基本的代码就够了。 三、思路分析 首先很容易想到，对于每一个“成语”，我们只需要它的首尾，中间两位其实不重要。 这就会想到有向图，一个词语中每个字的顺序是固定的，可以看成词首指向词尾。词语1 2 3 4，可以看成是1指向了4，于是，对于用例1的五个成语可以绘制成下面的图：
需要统计这个过程中经过的边数。 四、代码实现 如何建图？考虑map中每一个结点对应的是一个数组，数组中储存的是与之相连的结点。 queue q; map< int,vector > g; //建图 int m; scanf("%d",&m); int t1,t2; for (int i=0;i |
http://t.csdn.cn/fcTLy本文可以算是对学长已发帖子的进一步梳理，主要是一些个人理解，欢迎补充。
对于给定的用例，需要以1指向4这条边为起点，终点为10。【本文地址】
今日新闻 |
推荐新闻 |