搜索算法合集

By DijkstraPhoenix

深度优先搜索 (DFS)

引入

如果现在有一个迷宫，如何走路径最短？

方法

走迷宫最简单粗暴的方法式什么呢？当然是把所有路都走一遍啦！

如果是手动计算的话，可能会把你手指累得抽筋，但电脑不会，电脑具有强大的算力，这种暴力的事情当然是交给电脑做啦。

深搜的本质：一条路走到底，走到死胡同再往回走，回到上一个岔口继续走，直到找到正确的路

实际上，任何一条路都可以看做是一个只有一个岔口的分岔路，所以不需要把路和岔口分开计算。

那么刚才的例子应该是这么走（数字代表第几次尝试）实际上岔口走的顺序是任意的，方法不唯一。

概念：从死胡同返回的步骤叫做回溯

由于深搜不能保证第一次找到的路径为最短路径，所以需要统计所有路线

深搜一般使用递归实现，走过的每个位置都要打上标记，同一条路不能再走一遍

主算法代码:

<code>int maze[MAXN][MAXN];//存储迷宫 0表示当前节点可以走，1表示不能走

bool vis[MAXN][MAXN];//打标记

const int dx[]={1,0,-1,0};

const int dy[]={0,1,0,-1};//位移数组，分别对应 上右下左（如果是八向移动的话要改成对应的）

int n,m,stx,sty,edx,edy;//地图长宽以及起点和终点的坐标

int ans=0x7f7f7f7f;//最短距离，要初始化为极大值

void dfs(int x,int y,int z)//x和y是当前位置的坐标，z是走过的步数

{

if(x==edx&&y==edy)//到了终点

{

ans=min(ans,z);//更新答案（如果答案还是极大值，说明无法到达终点）

return;

}

vis[x][y]=true;//打标记

for(int i=0;i<4;i++)//枚举四个方向

{

int nx=x+dx[i],ny=y+dy[i];//下一个应该走到的位置

if(nx<1||nx>n||ny<1||ny>m)continue;//不能走出地图（这个要写在灵魂拷问的最前面，否则访问数组要越界）

if(maze[nx][ny]==1)continue;//不能卡墙里

if(vis[nx][ny])continue;//不能走你走过的路

dfs(nx,ny,z+1);//走到下一个节点

}

vis[x][y]=false;//重点！回溯时要清除标记！

}

例题

迷宫

洛谷 P1605

解法见上文

#include<iostream>

#include<cstring>

using namespace std;

int num=0;

int n,m,t,edx,edy,stx,sty;

int maze[10][10];

int vis[10][10];

int dx[]={0,1,0,-1};

int dy[]={1,0,-1,0};

void dfs(int x,int y)

{

vis[x][y]=1;

if(x==edx&&y==edy)

{

num++;

vis[x][y]=0;

return;

}

for(int i=0;i<4;i++)

{

int nx=x+dx[i];

int ny=y+dy[i];

if(nx<1||nx>n||ny<1||ny>m)continue;

if(maze[nx][ny]==1)continue;

if(vis[nx][ny]==1)continue;

dfs(nx,ny);

}

vis[x][y]=0;

}

int main(void)

{

int xjx,xjy;

memset(vis,0,sizeof(vis));

memset(maze,0,sizeof(maze));

cin>>n>>m>>t;

cin>>stx>>sty>>edx>>edy;

for(int i=1;i<=t;i++)

{

cin>>xjx>>xjy;

maze[xjx][xjy]=1;

}

vis[stx][sty]=1;

dfs(stx,sty);

cout<<num;

return 0;

}

八皇后问题

洛谷 P1219

本题的每一步都决定一个皇后的位置，由输出格式就可以看出，我们可以按每一列的顺序计算。一个皇后会独占一行、一列、两斜线，因为是按列计算的，不需要给列打标记，则需要 3 个标记数组。

（其实可以看一下洛谷上的题解）

#include<bits/stdc++.h>

using namespace std;

bool vis[15],vis1[35],vis2[35];

int n;

int nod[15];

int sum=0;

void dfs(int k)

{

if(k>n)

{

sum++;

if(sum<=3)//前3个要输出方案

{

for(int i=1;i<=n;i++)cout<<nod[i]<<" ";

cout<<endl;

}

return;

}

for(int i=1;i<=n;i++)

{

if(vis[i])continue;

if(vis1[i+k-1])continue;

if(vis2[i-k+13])continue;

vis[i]=true;

vis1[i+k-1]=true;

vis2[i-k+13]=true;//可以手动模拟一下行列坐标和斜坐标的关系，加13是防止计算出负数

nod[k]=i;//保存方案

dfs(k+1);

vis[i]=false;

vis1[i+k-1]=false;

vis2[i-k+13]=false;

}

}

int main(void)

{

cin>>n;

dfs(1);

cout<<sum;

return 0;

}

全排列问题

洛谷 P1706

按照题意模拟搜索即可

#include<iostream>

#include<cstdio>

using namespace std;

int n,a[1000],vis[1000];

void dfs(int step)

{

if(step==n+1)

{

for(int i=1;i<=n;i++)

{

printf("%5d",a[i]);//题目要求格式化输出

}

cout<<endl;

}

for(int i=1;i<=n;i++)

{

if(vis[i]==1)continue;

a[step]=i;

vis[i]=1;

dfs(step+1);

vis[i]=0;

}

}

int main(void)

{

cin>>n;

dfs(1);

return 0;

}

一些建议练习的题

求细胞数量

提示：联通块问题，不要清除标记，从每个未标记且是细胞的块出发，将整个块打上标记

小猫爬山

选数

单词接龙

--没写完呢--