简单搜索

前段时间都在做Kuangbin的专题一 简单搜索 ,好多都是边百度边看边想才写出来的,(学习嘛,都是从模仿开始的 == )还有些是看了自己也没写出来,现在重做一遍部分题,并对这个专题做个小结。

DFS

简述

  • DFS 全名 depth first search , 其主要思想就是:
    a.从当前点出发,不断进行递归,找到可以用的新的点
    b.如果新的点终点或是边界,就回溯一次,(即让上一个点成为下次递归的点)
    
    不断重复a、b两个步骤,直到最后无法回溯或者其他原因是跳出循环。

主要用于

  • 查找图中通路的条数,或者是放置某样东西的方法的种数。

注意

  • 对标记数组的处理,回溯之后对标记数组要进行还原。

    used[j] = true;
    dfs(index + 1, num-1);
    used[j] = false;
  • 递归的参数多样性。

    dfs(index + 1, num-1);
  • 递归结束的时间点。

    if(n-index<num){
    return;
    }
    if(index>n+1&&num!=0){
    return;
    }
    if(num==0){
    res++;
    return;
    }

以上例子:poj1321。

BFS

简述

  • BFS 全名 breadth first search , 其主要思想就是:
    a.从当前点出发,把所有的可到达的下一个点存放进队列中,除非找到终点跳出循环。
    b.取出队列的一个点,然后重复a步骤。
    
    最开始把起点放进队列中,执行b步骤。

主要用于

  • 寻找最短路径或者是到达终点的最小步数。

注意

  • 多起点。(例:hdu2612 、uva11624)

    • hdu2612:多次初始化并多次bfs.

      init(R,C);
      doit(ax, ay);
      init(R, C);
      doit(bx, by);
    • uva11624:一次将所有起点放进队列中,一次bfs

      if(str[i][j]=='F') {  
      F.xx=i;
      F.yy=j;
      F.t=0;
      F.isf=true;
      que.push(F);///将所有火坐标加入队列
      }
  • 路径存储。(例:poj3984)

    struct Node{
    int x, y;
    int preX, preY;
    };


    for (int i = 0; i < 4;i++){
    next.preX = temp.x;
    next.preY = temp.y;
    next.x = temp.x + dx[i];
    next.y = temp.y + dy[i];
    if(check(next.x,next.y)){
    vis[next.x][next.y] = false;
    Q.push(next);
    }
    }

    //倒序存储
    while(i--&&i>-1){
    i = j;
    //cout << "i" << i << endl;
    temp = V.at(i);
    roate.push_back(temp);
    for (j = i - 1; j > -1;j--){
    next = V.at(j);
    if(temp.preX == next.x && temp.preY == next.y){
    //cout << "j" << j<<endl;
    break;
    }
    }
    }
  • bfs双入口。(例:poj1426 + 二进制压缩)