t恤图案设计网站,怎么可以创建网站,中英文网站源码 免费,动画专业大学任务日期#xff1a;7.29
题目一链接#xff1a;110. 字符串接龙 (kamacoder.com)
思路#xff1a;将本题寻找附近的字符串等效于寻找四周的陆地#xff0c;即寻找周围与当前字符只有一位不同的字符串#xff0c;然后加入到队列中并标记上#xff0c;在此基础上要将字符…任务日期7.29
题目一链接110. 字符串接龙 (kamacoder.com)
思路将本题寻找附近的字符串等效于寻找四周的陆地即寻找周围与当前字符只有一位不同的字符串然后加入到队列中并标记上在此基础上要将字符串对应路径长度最后输出长度即可
代码
#include bits/stdc.h
//思路将本题寻找附近的字符串等效于寻找四周的陆地在此基础上要将字符串对应路径长度最后输出长度即可
using namespace std;
int main() {int n;cinn;string beginstr,endstr;cinbeginstrendstr;//定义一个字典集合方便直接查找unordered_setstring strlist;for(int i 0;i n;i ) {string str;cinstr;strlist.insert(str);}//定义一个地图记录以string为结尾的路径长度以便查找到endstr后直接返回长度//哈希表的插入和定义要注意unordered_mapstring,int visitedstr;//初始化visitedstr:插入beginstr并且设置路径长度为1visitedstr.insert(pairstring,int (beginstr,1));//进行bfsstd::queuestring que;que.push(beginstr);while(!que.empty()) {string cur que.front();que.pop();int path visitedstr[cur];//需要一个变量提前记录一下当前字符串的路径长度for(int i 0;i cur.size();i ){//依次换cur字符串的各个位置string neword cur;//如果换当前位置那么需要保证其他位置不动所以要重新定义一个newordfor(int j 0;j 26;j ) {//每个位置依次便利26个字母neword[i] j a;if(neword endstr) {coutpath 1;//第26行的作用在此体现return 0;}//确定递归终止条件if(strlist.count(neword) !visitedstr.count(neword)) {//strlist里面有当前字符串并且当前字符串没有被标记que.push(neword);//第28行作用在此体现visitedstr.insert(pairstring,int (neword,path 1));第26行的作用在此体现标记当前字符串并且当前路径1}}}}cout0;return 0;
}
难点1.哈希表集合和map的创建。集合unordered_setstring strlist; map:unordered_mapstring,int visitedstr;
2.哈希表的插入操作visitedstr.insert(pairstring,int (beginstr,1));
3.哈希表map的含义以string为结尾的路径长度int.
4.用bfs求最短路径原因在于它是一圈一圈的遍历当到达目标点时当前路径长一定是最短路径。
,5.在每次便利一个新的string时要用path记录当前路径长度 题目二链接
思路
代码
难点
解释细节1 题目三链接
思路
代码
难点
解释细节1
