深搜与广搜的C++模板
2024-09-30
343
1.深搜深搜类似于树的先序遍历,通过每次访问一个点,无法继续搜索时进行回溯的思想解题intn,m;//记录边界int mov[4][2] = {1,0,-1,0,0,1,0,-1};int vis[N][N],mapp[N][N];int s = 0;//记录步数/时间void DFS(int x,int y){if(x=endx&&y==endy)//

1.深搜

深搜类似于树的先序遍历,通过每次访问一个点,无法继续搜索时进行回溯的思想解题































int n,m;//记录边界int mov[4][2] = {1,0,-1,0,0,1,0,-1};int vis[N][N],mapp[N][N];int s = 0;//记录步数/时间
void DFS(int x,int y){    if(x = endx && y == endy)//条件判断        return ;    for(int i = 0; i<4; i++)//题意不一定是移动某个位置,可能就没办法循环,直接写搜索条件,满足条件就DFS();    {        int xx = x+mov[i][0];        int yy = y+mov[i][1];        if(xx>=n||xx<0||yy>=m||yy<0||vis[xx][yy])//判断是否越界            continue;        else        {            s++;//每搜一次加一            vis[xx][yy] = 1;            DFS(xx,yy);            //根据题意是否回溯            vis[xx][yy] = 0;            s--;        }    }}



2.广搜

广搜和深搜不同,广搜思想是遍历每一个顶点时,依次遍历其所有的邻接点,然后再从这些邻接点出发,同样依次访问它们的邻接点。按照此过程,直到图中所有被访问过的顶点的邻接点都被访问到














































int m,n;int mov[4][2] = {1,0,-1,0,0,1,0,-1};int vis[N][N],mapp[N][N];
struct node{    int x,y,step;};
int BFS(int x,int y)//传入起点{    //初始化条件    memset(vis,o,sizeof(vis));    queue<node>q;  //广搜要用队列    node a,next;    a.x = x;    a.y = y;    a.step = 0;    vis[x][y] = 1;    q.push(a);    //搜索    while(!q.empty())    {        a = q.front();        q.pop();        if(mapp[a.x][a.y] == 'E')//结束条件            return a.step;        for(int i = 0; i<4; i++)        {            int xx = a.x+mov[i][0];            int yy = a.y+mov[i][1];            if(xx>=n||xx<0||yy>=m||yy<0||vis[xx][yy])//限制条件                continue;            else            {                next.x = xx;                next.y = yy;                next.step = a.step+1;                vis[xx][yy] = 1;                q.push(next);            }        }    }    return -1;//没有搜到/不满足条件}