搜索

总结算法常见问题中关于搜索的相关方法和注意要点

枚举

找准条件即可

广度优先搜索（BFS）

主要完成状态的转移，不断拓展状态

基础模版例题

示例代码：

#include<iostream>
#include <queue>
using namespace std;
bool mark[50][50][50];//标记数组
int maze[50][50][50];//保存立方体信息
struct N{
    int x,y,z;//位置坐标
    int t;//所需时间
};
queue<N> Q; //队列，队列中的元素为状态
int go[][3]={
    //用于坐标变换，六个方向
    1,0,0,
    -1,0,0,
    0,1,0,
    0,-1,0,
    0,0,1,
    0,0,-1
};
int BFS(int a,int b,int c){
  while(!Q.empty()){
      N now=Q.front();
      Q.pop();
      for(int i=0;i<6;i++){
        //依次扩展其六个相邻结点
        int nx=now.x+go[i][0];
        int ny=now.y+go[i][1];
        int nz=now.z+go[i][2];
        if(nx<0||nx>=a||ny<0||ny>=b||nz<0||nz>=c)  continue;
        //若新坐标在立方体外，则丢弃该坐标
        if(maze[nx][ny][nz]==1) continue;//若该位置为墙，则丢弃该坐标
        if(mark[nx][ny][nz]==true) continue;//已经标记过，丢弃该坐标
        //队列中放入新结点
        N tmp;
        tmp.x=nx;
        tmp.y=ny;
        tmp.z=nz;
        tmp.t=now.t+1;//耗时
        Q.push(tmp);
        mark[nx][ny][nz]=true;//标记该结点
        if(nx==a-1&&ny==b-1&&nz==c-1)
           return tmp.t;
        //若该坐标即为终点，可直接返回其耗时
      }
  }
  return -1;//若所有状态查找完后，仍得不到所需坐标，则返回-1
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        int a,b,c,t;
        cin>>a>>b>>c>>t;
        for(int i=0;i<a;i++)
        for(int j=0;j<b;j++)
        for(int k=0;k<c;k++){
            cin>>maze[i][j][k];//输入立方体信息
            mark[i][j][k]=false;//初始化标记数组
        }
        while(!Q.empty())  Q.pop();//清空队列
        mark[0][0][0]=true;//标记起点
        N tmp;
        tmp.t=tmp.x=tmp.y=tmp.z=0;//初始状态
        Q.push(tmp);//将初始状态放入队列
        int res=BFS(a,b,c);//广度优先搜索
        if(res<=t)  cout<<res;//若所需时间符合条件，则输出
        else cout<<"-1"<<endl;
    }
    return 0;
}

例题2，注重状态转移

示例代码

#include<iostream>
#include <queue>
using namespace std;
struct N{
    int a,b,c;//每个杯子中可乐的体积
    int t;//得到该体积组倾倒次数
};
queue<N> Q;//队列
bool mark[101][101][101];
void AtoB(int &a,int sa,int &b,int sb)
{
    //倾倒函数，由容积为sa的杯子倒往容积为sb的杯子
    //a，b，初始时为原始杯子中可乐的体积，
    //函数调用完毕后，为各自杯子中可乐的新体积
    if(sb-b>=a) 
    {
        //若a可以全部倒到b中
        b+=a;
        a=0;
    }
    else 
    {
        a-=sb-b;
        b=sb;
    }
}

int BFS(int s,int n,int m)
{
    while(!Q.empty())
    {
        N now=Q.front();//拿出队头状态
        Q.pop();
        int a,b,c;//a,b,c临时保存三个杯子中可乐体积


        //可能的状态 a->b
        a=now.a;
        b=now.b;
        c=now.c;
        AtoB(a,s,b,n);//由a倾倒向b
        if(mark[a][b][c]==false)
        {
            //若该体积组尚未出现
            mark[a][b][c]=true;//标记该体积组
            N tmp;
            tmp.a=a;
            tmp.b=b;
            tmp.c=c;
            tmp.t=now.t+1;//生成新的状态
            if(a==s/2&&b==s/2) return tmp.t;
            if(c==s/2&&b==s/2) return tmp.t;
            if(a==s/2&&c==s/2) return tmp.t;
            //若该状态已经为平分状态，则直接返回该状态的耗时
            Q.push(tmp);//否则放入队列
        }


        //可能的状态b->a
        a=now.a;
        b=now.b;
        c=now.c;
        AtoB(b,n,a,s);//由b倾倒向a
        if(mark[a][b][c]==false)
        {
            //若该体积组尚未出现
            mark[a][b][c]=true;//标记该体积组
            N tmp;
            tmp.a=a;
            tmp.b=b;
            tmp.c=c;
            tmp.t=now.t+1;//生成新的状态
            if(a==s/2&&b==s/2) return tmp.t;
            if(c==s/2&&b==s/2) return tmp.t;
            if(a==s/2&&c==s/2) return tmp.t;
            //若该状态已经为平分状态，则直接返回该状态的耗时
            Q.push(tmp);//否则放入队列
        }


        //可能的状态a->c
        a=now.a;
        b=now.b;
        c=now.c;
        AtoB(a,s,c,m);//由a倾倒向c
        if(mark[a][b][c]==false)
        {
            //若该体积组尚未出现
            mark[a][b][c]=true;//标记该体积组
            N tmp;
            tmp.a=a;
            tmp.b=b;
            tmp.c=c;
            tmp.t=now.t+1;//生成新的状态
            if(a==s/2&&b==s/2) return tmp.t;
            if(c==s/2&&b==s/2) return tmp.t;
            if(a==s/2&&c==s/2) return tmp.t;
            //若该状态已经为平分状态，则直接返回该状态的耗时
            Q.push(tmp);//否则放入队列
        }


        //可能的状态 c->a
        a=now.a;
        b=now.b;
        c=now.c;
        AtoB(c,m,a,s);//由c倾倒向a
        if(mark[a][b][c]==false)
        {
            //若该体积组尚未出现
            mark[a][b][c]=true;//标记该体积组
            N tmp;
            tmp.a=a;
            tmp.b=b;
            tmp.c=c;
            tmp.t=now.t+1;//生成新的状态
            if(a==s/2&&b==s/2) return tmp.t;
            if(c==s/2&&b==s/2) return tmp.t;
            if(a==s/2&&c==s/2) return tmp.t;
            //若该状态已经为平分状态，则直接返回该状态的耗时
            Q.push(tmp);//否则放入队列
        }


        //可能的状态 b->c
        a=now.a;
        b=now.b;
        c=now.c;
        AtoB(b,n,c,m);//由b倾倒向c
        if(mark[a][b][c]==false)
        {
            //若该体积组尚未出现
            mark[a][b][c]=true;//标记该体积组
            N tmp;
            tmp.a=a;
            tmp.b=b;
            tmp.c=c;
            tmp.t=now.t+1;//生成新的状态
            if(a==s/2&&b==s/2) return tmp.t;
            if(c==s/2&&b==s/2) return tmp.t;
            if(a==s/2&&c==s/2) return tmp.t;
            //若该状态已经为平分状态，则直接返回该状态的耗时
            Q.push(tmp);//否则放入队列
        }


        //可能的状态c->b
        a=now.a;
        b=now.b;
        c=now.c;
        AtoB(c,m,b,n);//由c倾倒向b
        if(mark[a][b][c]==false)
        {
            //若该体积组尚未出现
            mark[a][b][c]=true;//标记该体积组
            N tmp;
            tmp.a=a;
            tmp.b=b;
            tmp.c=c;
            tmp.t=now.t+1;//生成新的状态
            if(a==s/2&&b==s/2) return tmp.t;
            if(c==s/2&&b==s/2) return tmp.t;
            if(a==s/2&&c==s/2) return tmp.t;
            //若该状态已经为平分状态，则直接返回该状态的耗时
            Q.push(tmp);//否则放入队列
        }
    }
    return -1;
}

int main()
{
    int s,n,m;
    while(cin>>s>>n>>m&&s&&n&&m)
    {
        if(s%2==1) {
            //若s为奇数不可能平分，直接输出NO
            cout<<"NO"<<endl;
            continue;
        }
        for(int i=0;i<=s;i++)
         for(int j=0;j<=n;j++)
          for(int k=0;k<=m;k++)
             mark[i][j][k]=false;
             //初始化状态
        N tmp;
        tmp.a=s;
        tmp.b=0;
        tmp.c=0;
        tmp.t=0;
        while(!Q.empty()) Q.pop();
        Q.push(tmp);//将初始状态放入队列
        mark[s][0][0]=true;//标记初始状态
        int rec=BFS(s,n,m);//广度优先搜索
        if(rec==-1) cout<<"NO"<<endl;
        else cout<<rec<<endl;
    }
    return 0;
}

递归

递归是一种十分常用的编码技巧，所谓即递归即函数调用
函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归方式。
同时，为了不使这样的递归无限的发生，我们必须设定递归的出口，即当函数到达某种条件时停止递归。

模版例题：

主要代码：

Long Long F(int num){
   if(num==1) return 2;
   else return 3*F(num-1)+2;
}

示例1：素数环

题目大意为由给定的 1 到 n 数字中，将数字依次填入环中，使得环中任意两 个相邻的数字间的和为素数。

对于给定的 n，按字典序由小到大输出所有符合条 件的解（第一个数恒定为 1）

为了解决该问题，我们可以采用回溯法枚举每一个值。当第一个数位为 1
确定时，我们尝试放入第二个数，使其和 1 的和为素数，放入后再尝试放入第三 个数，使其与第二个数的和为素数，直到所有的数全部被放入环中，且最后一个 数与 1 的和也是素数，那么这个方案即为答案，输出；若在尝试放数的过程中， 发现当前位置无论放置任何之前未被使用的数均不可能满足条件，那么我们回溯 改变其上一个数，直到产生我们所需要的答案，或者确实不再存在更多的解。 为了实现这一回溯枚举的过程，我们采用递归的形式：

#include<iostream>
#include<cstring>
using namespace std;

int ans[22];//保存环中每一个被放入的数
bool hashnum[22];//标记之前已经被放入环中的数
int n;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};
bool judge(int x)
{//判断是否是素数
    for(int i=0;i<13;i++)
      if(prime[i]==x) return true;
    return false;
}
void check()
{
    //检查输出由回溯枚举得到的解
    if(judge(ans[n]+ans[1])==false) return;
    //判读最后一个数和第一个数
    for(int i=1;i<=n;i++)
    {
        if(i!=1) cout<<" ";
        cout<<ans[i];
    }
    cout<<endl;
}
void DFS(int num)
{
    //递归枚举，num为当前已经放入环中的数字
    if(num>1) //当放入的数字大于一个时
      if(judge(ans[num]+ans[num-1])==false)
         return;
    //判断最后两个数字的和是否为素数，若不是则返回枚举第num个数
    if(num==n){
        //若已经放入了n个数
        check();//检查输出
        return;//返回，继续枚举下一组解
    }
    for(int i=2;i<=n;i++)
    {
        //放入一个数
        if(hashnum[i]==false){
            hashnum[i]=true;//标记i为已使用
            ans[num+1]=i;//将这个数字放入ans数组中
            DFS(num+1);//继续尝试放入下一个数
            hashnum[i]=false;//当回溯回枚举该位数字时，将i标记为未使用
        }
    }
}

int main()
{
    int cas=0;//记录Case数
    while(cin>>n&&n)
    {
        cas++;
        for(int i=0;i<22;i++)
           hashnum[i]=false;
        //初始化
        ans[1]=1;//第一个数字恒定为1
        cout<<cas<<endl;
        hashnum[1]=true;//标记1被使用
        DFS(1);//继续尝试放入下一个数字
        cout<<endl;
    }
    return 0;
}

示例2 洪泛 遍历图

题目大意：在给定的 n*m 图中，确定有几个@的块。块符合以下条件，其
中的任意对@均互相直接或间接连通，两个@直接相邻或者对角相邻即被视为连通。
计算最后总共有几个连通块

输入

The input file contains one or more grids. Each grid begins with a line containing
m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket.
1 1 
*
3 5
*@*@* 
**@** 
*@*@* 
1 8
@@****@* 
5 5
****@ 
*@@*@ 
*@**@ 
@@@*@ 
@@**@ 
0 0

输出

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
0 
1 
2 
2

代码

#include <iostream>
using namespace std;
char a[101][101];
bool mark[101][101];
int n, m;
void init()
{
    for (int i = 0; i < 101; i++)
        for (int j = 0; j < 101; j++)
        {
            a[i][j] = 0;
            mark[i][j] = false;
        }
}
void DFS(int h, int l)
{
    if (h > n || l > m)
        return;
    for (int i = -1; i <= 1; i++)
        for (int j = -1; j <= 1; j++)
        {

            int newh = h + i;
            int newl = l + j;
    
            if (newh < 1 || newh > n || newl < 1 || newl > m || mark[newh][newl] == true)
                continue;
            if (a[newh][newl] == '*')
                continue;

            mark[newh][newl] = true;
            DFS(newh, newl);
        }
}

int main()
{
    while (cin >> n && n)
    {
        cin >> m;
        init();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> a[i][j];
        int ans = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                if (!mark[i][j] && a[i][j] == '@')
                {
                    mark[i][j] = true;
                    DFS(i, j);
                    ans++;
                }
            }

        cout << ans << endl;
    }
    return 0;
}

深度优先搜索 DFS

首先回顾之前已经介绍过的广度优先搜索。在由状态的转移和扩展构成的解答树中，
广度优先搜索按照层次遍历所有的状态，直到找到我们需要的状态。 与其相对的，假如我们改变对解答树的遍历方式，改为优先遍历层次更深的状态，直到遇到一个状态结点，其不再拥有子树，则返回上一层，
访问其未被访 问过的子树，直至解答树中所有的状态都被遍历完毕。
这个过程，类似于树的前序遍历。

由于其缺少了广度搜索中按层次递增顺序遍历的特性。
所以当深度优先搜索 搜索到我们需要的状态时，其不再具有某种最优的特性。
所以，在使用深度优先 搜索时，我们更多的求解有或者没有的问题，即对解答树是否有我们需要的答案 进行判定，
而一般不使用深度优先搜索求解最优解问题

示例 迷宫 经典问题

题目大意：有一个 N*M 的迷宫，包括起点 S，终点 D，墙 X，和地面，0
秒时主人公从 S 出发，每秒能走到四个与其相邻的位置中的一个，且每个位置被 行走之后都不能再次走入，问是否存在这样一条路径使主人公在 T 秒时刚好走 到D。

样例输入输出

第一行代表N，M，T，接下来N行M列就是数组，也就是此题迷宫的地图

4 4 5 
S.X. 
..X. 
..XD 
....
3 4 5 
S.X. 
..X. 
...D 
0 0 0

输出：
NO 
YES

代码

#include <iostream>
using namespace std;
int N, M, T;
char a[8][8];
int dir[][2] = {
    -1, 0,
    0, -1,
    0, 1,
    1, 0};
bool mark[8][8];
bool flag;
void DFS(int x, int y, int t)
{
    if (a[x][y] == 'D')
    {
        flag = true;
        return;
    }
    else if (t > T)
        return;
    else
    {
        for (int i = 0; i < 4; i++)
        {
            int newx = x + dir[i][0];
            int newy = y + dir[i][1];
            if (newx < 1 || newx > N || newy < 1 || newy > M)
                continue;
            if (a[newx][newy] == 'X')
                continue;
            if (!mark[newx][newy])
            {
                mark[newx][newy] = true;
                DFS(newx, newy, t + 1);
                mark[newx][newy] = false;
            }
        }
    }
}

int main()
{
    while (cin >> N >> M >> T && N && M && T)
    {
        flag = false;
        int marki, markj;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
            {
                mark[i][j] = false;
                cin >> a[i][j];
                if (a[i][j] == 'S')
                {
                    marki = i;
                    markj = j;
                }
            }
        mark[marki][markj] = true;
        DFS(marki, markj, 0);

        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

其他问题

八皇后

主要在于判断对角线是否相同

/*非常朴素的八皇后问题，问题规模也已经框定好了，只要把每次得到的列号转化成要比较的十进制数字即可*/

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

vector<int> solut;            //用来放最终的结果
int position[9];            //行号从1开始，其中下标代表行号，其中存放的内容代表列号

void DFS(int row);

int main()
{
    DFS(1);                    //直接从第一行开始放
    sort(solut.begin(), solut.end());    //这里应该不用sort因为得到的solution应该都是从小到大
    int n;
    while (scanf("%d", &n) != EOF)
    {
        printf("%d\n", solut[n - 1]);    //因为vector是从0开始的    
    }
    return 0;
}

void DFS(int row)            //row代表要放入的行号,逐行放入，因为要用的是列号，而且按照习惯都是一列一列计算的
{
    if (row == 9)            //row==9意味着从1~8行全都放入,已完成解
    {
        int temp = 0;
        for (int i = 1; i <= 8; i++)
        {
            temp += position[i] * pow(10, 8 - i);    
        }
        solut.push_back(temp);                        //把得到的solution放进vector
    }

    else
    {
        for (int i = 1; i <= 8; i++)
        {
            position[row] = i;        //i在这里代表列号
            bool flag = true;        //用一个标志位来标记，是否冲突
            for (int j = 1; j <  row; j++)
            {
                if (position[row] == position[j] || row - position[row] == j - position[j] || row + position[row] == j + position[j])
                {
                    flag = false;
                    break;
                }        //这里的判断条件j - position[j]会把同一主对角线标记为同一个数字，与row - position[row]同时计算就能判断是否冲突
            }//for
            if (flag)
                DFS(row + 1);
        }
    }//endif
}//DFS