本周搜索总结之一些应用

本周还是接着上次看费老给的搜索例题的进度一直往下看，看到了第六十个左右，呃也并不是全都看懂了还有一堆没研究透的。（不知道是有心还是无心，果然上边开始的都是简单题哈哈）往下就比上边的题难，还和一些各种别的东西结合，有的甚至连题都读不懂了，因为有一些没了解过的新名词。（这周一上课就让费老逮住了说我投入的时间还是不够，感觉这周一线下比线上的时间更少了，和上次不同这次举了几个典型的例题，几乎从每个题中我都能学到一点东西，所以这次我借用这些搜索的应用来说一下我的收获

1、

马的遍历

说这个题是因为感觉这个题和其他的普通的题不同，其他的题可能是求从某点到某点所需要的最短步数，只需要一直搜索然后标记然后回溯就可，但是这个题不一样，它是要求输出到达棋盘上每一个点分别所需要的最短步数，所以可能要对点进行特殊处理

当我看到这个题第一眼，就想到用dfs写，但当我写完测试数据时发现，有个别位置的数字比答案要多好几，但是大部分数据都是对的，于是我才想到了这一原因，一定是到达别的点的途中再次经过这个点时，这个点的步数和被累加了，所以我一直在想怎么解决不让他累加（但是也不能走完这个路后就清零，因为每个点记录的步数是要保留到最后输出的），改来改去一直错，最后看了一眼题解发现有个好方法就是在判断下一步数组是否越界的时候同时也判断if（此时的步数+1<下一步的点所对应的步数||下一步还未被走过），这两个条件只要成立一个就好，这样就完全不用担心步数会被累加了 代码如下

于是乎......

#include<bits/stdc++.h>
using namespace std;
int ans[410][410],flag[410][410];
int n,m,nextx,nexty,sx,sy;
int dx[8]={2,2,-2,-2,1,1,-1,-1},dy[8]={1,-1,1,-1,2,-2,2,-2};
void dfs(int x,int y,int cmp)
{ans[x][y]=cmp;
for(int i=0;i<8;i++)
{nextx=x+dx[i];
nexty=y+dy[i];
if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m&&((ans[nextx][nexty]==-1)||cmp+1<ans[nextx][nexty]))
//关键判断，不仅防数组越界同时保证下一步步数要小于下一步已记录步数
{
dfs(nextx,nexty,cmp+1);}
}
}
int main(){
cin>>n>>m>>sx>>sy;
ans[sx][sy]=0;
memset(ans,-1,sizeof(ans));//这也是从题解学到的，由于起点是0步所以赋值-1
dfs(sx,sy,0);
//本来是全部赋为0的 但忽略了起点
for(int i=1;i<=n;i++)
//而且后来才发现全赋为-1的话输出的时候就不用判断不能到达的点了哈哈哈
{for(int j=1;j<=m;j++)
{printf("%-5d",ans[i][j]);
}printf("n");}
return 0;
}

but......虽然提交之后有绿色的但是超时了  才意识到n<=400,太大了！所以要用bfs！！！不能用dfs！所以又写了一次bfs 核心代码如下 （血淋淋的教训，最不喜欢的就是从头开始写代码，所以下次一定要先看请数据范围）

void bfs(int x,int y,int step){
a[x][y] = step;b[x][y] = 0;
queue<t>q;
ma.x = x;ma.y = y;
q.push(ma);
while (!q.empty()){
top=q.front();
q.pop();
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
if (abs(dx[i])!=abs(dy[j])){
int newx=top.x+dx[i],newy=top.y+dy[j];
if (newx<1||newx>n||newy<1||newy>m) continue;
if (b[newx][newy]){
ma.x=newx;ma.y=newy;q.push(node);
b[newx][newy] = 0; a[newx][newy] = a[top.x][top.y]+1;
}}}}//把四个中括号写一块了尽量减小在这的占用空间

2、

这个题与普通题也不怎么相同，读懂题意后没有想到用搜索竟可以做，虽然是搜索题但是也没想出来怎么用搜索去想思路，看了题解才知道是用dfs从下表面的洞开始搜索，一直向上以洞相连为条件搜索，（两圆心距离小于等于半径和）直到圆心z坐标+r大于等于h，感觉这种题很考验人的思维，不看题解思路也真不怎么能想起来。搞掉这个题主要是有两点：首先是判断两个洞是否相连，即两洞之间距离是否小于等于两球半径之和；其次就是需要判断判老鼠能否从穿过整个奶酪到达上表面，要从最下面的一个洞开始走，走过的洞标记，但如果前方不能再走了还会返回这个洞寻找下一个和这个洞相连的别的洞，这样的话就可以将每一个能和底边连接到的洞全部判断一遍，只要最后能一直走到上表面就可以出来。

3、

这是一道和数学思维紧密相连的dfs题，实际是用到了杨辉三角形，题目没有提到，是需要分析发现的（但是不看题解真的想不到和这有关系qwq~） 是一个将搜索和数学,剪枝,回溯集为一体的一个题

将题意给的数字上下颠倒过来就会发现就是隐藏的杨辉三角，最后得出的规律就是最终答案=该位杨辉三角中的数*该数（硬是把题解看了好几遍也遍也没有特别懂但是知道规律后也才刚刚看懂了）

4、

题解千千万，但有一个特别戳到了我

这个题的大意是每个数字都对应多个字母，然后给出多种合适的字母排序，再给出一组数字求转换成字母后有无合适的字母排序。我遇到这个题时只想到了一个二重循环，依次列举数字转换后的每一种排序依次和题目给出的许多有效字母排序比较，如果找到相同的就输出了，但是超时，一定会超时。看了题解了解到可以用stl来做这个题，用map，map[key]=value,一个键只能对应一个值，但一个值能被多个键所映射，所以可以让每个字母当键，然后对应的数字作为值，所以找答案时只需要从第一位开始判断key所对应的value数字是否相等即可，就不需要二重循环挨个找了，一下就将时间复杂度缩小了几倍 。（在csdn上搜了搜才知道好像map可以一个键对应多个值，但是需要用别的东西去实现）

void init()
{
m['A']=2;m['B']=2;m['C']=2;m['D']=3;m['E']=3;m['F']=3;
m['G']=4;m['H']=4;m['I']=4;m['J']=5;m['K']=5;m['L']=5;
m['M']=6;m['N']=6;m['O']=6;m['P']=7;m['R']=7;m['S']=7;
m['T']=8;m['U']=8;m['V']=8;m['W']=9;m['X']=9;m['Y']=9;
m['Q']=0;m['Z']=0;
}
bool check()
{
int lenw=strlen(word);
if(lenw!=len) return 0;
for(int i=0;i<len;i++)
if(m[word[i]]!=(int)(num[i]-'0')) return 0;
//就是这句戳中的我！！！word[i]是输入时的有效字符串中的字母，
//所以m[word[i]]代表的就是这个字母对应的数字，而且三个不同字母对应一个数字
//所以不管多少字母最后对应下来最多就是十个数字，只要这一串的每个数字对应相同就符合条件
//感觉大大降低了时间复杂度
return 1;}

5、多个结点之间互相连接的不同问题

1、P1294 高手去散步

2、P4017 最大食物链计数

3、P6691 选择题

4、P1037 产生数

这几个题每一个题都有自己的独特之处都考到了不同的知识点，感觉还有许多可以再继续深究

（1）无向图问题

第一题是最简单的，最主要的是没有方向性！两节点之间可以相互去，只需要在代码中实现标记谁与谁是相连的即可，核心如下

void dfs(int x,int y)//x,y是两个景点，这里没写搜索边界，主要展示核心部分
{for(int i=1;i<=n;i++){
if(!a[x]&&s[y][i]!=0){//如果没有来过，且我们找到了和它连接的下一个点
sum+=s[x][y];//记录走过的路程
a[x]=1;//标记我们来过这个景点
dfs(y,i);//搜索下两个景点
sum-=s[x][y];//回溯
a[x]=0;}}

（2）有向图问题

第二题和第一题不同，第二题是食物链，明显的具有方向性，从题解中我又了解到一个拓扑排序，看到题解全都在说这就是拓扑排序，那我肯定要去搜一搜这是什么意思啦，这个我也有收获，也懂了一些，但我现在的理解也可能有些浅

拓扑排序是在一个有向图中，对所有的节点进行排序，必要求有一个节点指向它前面的节点（我感觉这一句话说的很好就借过来了，下面都是我自己的理解）。但是不能用在环中，因为环是个封闭的转一圈又回到起点，不符合他的定义。有向线段连接起来的图形还不能有环，这不就是妥妥的食物链嘛。果然，知识积累的多了，新问题便会有了眉目。用队列实现。思想就是先找到只有输出（我自己定义的觉的说着方便，就是指向别的点）没有输入（即别的点指向他）的点入队列，再找他指向的下一个点，然后第一个点出队的同时消去这个点的所有输出方向，（这样才能再找下一个点的同时也找和第一个点一样没有输入），然后再根据和找第一个点一样的要求找下一个点，这条路找到最后变顺其而然的找到了一条食物链。

（3）第4题本来想单独放出来的，因为从第四题中学习到了一个新的可以解决类似题的算法：Floyd，主要是在这个题解中看到很多人用这个，我也不懂什么意思，就去CSDN搜了搜，发现还挺好理解的也很好实现，（要不然很可能看不下去这个新东西了嘿嘿）一般是在有许多结点然后许多点两两之间有联系， 然后用这个算法可以用于求出每两点之间的最短或最长路径（结果学习完之后发现好像上面这几个两段连通的路径问题好像都可以用这个来解决，都是一类题好像，但我也没实现不知道行不行）

原理就是利用（i，k）两点的中间结点j，然后比较s（i->k+k->j）和s（i->j）的大小然后更新最值，核心代码如下

for(int k = 1 ; k <= n ; k ++)
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n ; j ++)
{if(s[i][j] > s[i][k] + s[k][j])
s[i][j] = s[i][k] + s[k][j]; }

小收获

ps1：看题解中 学到了一个标记：例如在代码中某处加入   jie:  ， 后面任意处用到jie后面的语句时，则 goto jie；即可跳到标记处

ps2：如果是只输出一条路径的题，一般定义的book数组不需要取消标记

本周心得体会：

主要是遇到新问题新知识的解决，

感觉越往后难度越大，更何况有些水题不需要看，正好印证了这周上课时费老所说的想一想看到新问题新知识时如何解决，感觉对这个印象应该还挺深的，因为这周看题解让我看到就算是一个典型搜索算法的题也会和其他许多别的知识点结合，如果那个知识点没有捅破他的意思，那估计也找不到破题口，所以在精读某一算法的同时遇到一些新问题新知识点不能退缩，要自己动手动脑去想通它，搞懂它，在最开始看见方向数组时（虽然现在看来它是多么简单）我都没怎么懂它什么意思，后来见得多了自然而然的懂了。

单从我这几周看的搜索例题来看，它会和数学中的杨辉三角形结合，和stl结合，和贪心结合，和二叉树结合，和并查集结合，和无向图有向图（一般好像用拓扑排序）结合等等。所以当我看到这样的题时，我会先搜一下搞懂我不会的知识点是什么意思，虽然刚开始看也看不多透，但是有的确实是看得多了，好像就自然而然的有点悟了。比如以前看的题大多都是迷宫从起点到终点，但是这周见了好多是线型的许多点两端都和别的点连通的题，开始很蒙圈，看了好几道之后就有点悟了，还学到了一个结点间求最短路新算法floyd，也是在某个题中看到许多人都用这个解题我就去搜了一下它的原理，结果还真的看懂这个了，有收获。这同时也印证了费老说的看不懂的就看上五遍，十遍，最后一定能看懂！！！我现在也非常相信这句话。（虽然有悟的但是还是有好多没悟的，带无向图的题还是没怎么搞懂，和二叉树有关系的主要是感觉树里面有太多名词了什么儿子什么祖先什么度的，看着看着就忘了忘着忘着看题解时就蒙了，反正下周费老也要讲数据结构了正好凑这机会下周把这两类搞懂再写这两类题！！）明天开始就要迎来早晚自习了芭比Q，更要不停的挤时间了，下周的目标是把给的题剩下的以及这周没看懂的全看完看透！

最后

以上就是无限眼神为你收集整理的本周搜索总结之一些应用的全部内容，希望文章能够帮你解决本周搜索总结之一些应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。