啊哈算法（4）—万能的搜索

痛定思痛。 2022-05-15 01:27 283阅读 0赞

**深度优先搜索DFS**  
深度优先搜索的关键在于解决“当下该如何做”。至于下一步怎么做与当下该如何做是一样的。深度优先搜索的基本模型：

void dfs(int step)
    {
        判断边界
        尝试每一种可能for(i=1;i<=n;++i)
        继续下一步dfs(step+1);
    }

例1：求1到n的全排列，n为1~9之间任意一个数。

//求1到n的全排列  想相有n个盒子往里面放牌
    #include<iostream>
    
    using namespace std;
    
    int a[10], book[10], n; 
    
    void dfs(int step)  //站在第step个盒子前面
    {
        if (step == n+1) //边界条件  到n+1时说明前面都已经放好
        {
            for (int i = 1; i <= n; ++i)
            {
                cout << a[i] << " " ;
            }
            cout << endl;
        }
        else
        {
            for (int i = 1; i <= n; ++i)
            {
                if (book[i] == 0)  //对每一种还没有尝试的进行尝试 为0的时候表示第i种还没有进行尝试
                {
                    book[i] = 1;    
                    a[step] = i;
                    dfs(step + 1);
                    book[i] = 0;   //尝试完之后要收回
                }
            }
        }
    }
    
    int main()
    {
        cin >> n;//n位于1到9之间
        dfs(1);//现在站在第1个前面
        getchar();
    }

例2：有1到9几个号码牌，将其填入括号中，使得（）（）（）+（）（）（）=（）（）（）。  
其实就是对其求个全排列，并且判断一下a\[1\]\*100+a\[2\]\*10+a\[3\]+a\[4\]\*100+a\[5\]\*10+a\[6\]=a\[7\]\*100+a\[8\]\*10+a\[9\]是否满足，不在列举出代码。

例3：解救小哈，输入几行数，第一行两个数n，m。接下来的n行m列为迷宫，其中0表示可以走的地方，1表示障碍物。最后一行4个数，前两个表示迷宫的入口的x和y的坐标。后两个为小哈的位置。求出最短的步数。

#include<iostream>
    #define INT_MAX 0x7fffffff;
    using namespace std;
    
    int a[51][51], book[51][51], min = INT_MAX;
    
    int n, m, p, q;
    void dfs(int x, int y, int step)
    {
        int next[4][2] = { { 0,1 },//向右走 
                            { 1,0 },//向下走
                            { 0,-1 },//向左走 
                            { -1,0 } };//向上走
        if (x == p&&y == q)
        {
            if (step < min)
                min = step;
        }
        else
        {
            for (int k = 0; k <= 3; ++k)   //枚举四种走法
            {
                int tx = x + next[k][0];
                int ty = y + next[k][1];
                if (tx<1 || tx>n || ty<1 || ty>m) //判断是否在迷宫范围内
                    continue;
    
                if (a[tx][ty] == 0 && book[tx][ty] == 0) //判断是否为障碍物或者已经走过  
                {
                    book[tx][ty] = 1;
                    dfs(tx, ty, step + 1);
                    book[tx][ty] = 0;
                }
            }
        }
    }
    
    int main()
    {
        cin >> n >> m;
        int startx, starty;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> a[i][j];
        cin >> startx >> starty;
    
        //从起点开始搜索 标记为已经走过
        book[startx][starty] = 1;
        dfs(startx, starty, 0);
        cout << min << endl;
    
    }

**广度优先搜索BFS**  
BFS是一种层层递进的搜索方式，通常通过队列来完成，队列中存放的节点层次不超过一。  
例1：与上面一个例子相同，不过这里将会采用广度优先搜索的方法完成，这里使用一个数组来模拟一个队列。

#include<iostream>
    #define INT_MAX 0x7fffffff;
    using namespace std;
    
    struct note
    {
        int x;   //横坐标
        int y;   //纵坐标
        int f;   //父亲在队列中的编号，用于输出路径
        int s;   //步数
    };
    
    int main()
    {
        int a[51][51], book[51][51];
        struct note que[2501];// 地图大小为50*50，因此队列中的元素不会超过2500个
        int n, m, p, q;
        cin >> n >> m;
        int startx, starty;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> a[i][j];
        cin >> startx >> starty>>p>>q;
    
        int next[4][2] = { { 0,1 },//向右走 
                            { 1,0 },//向下走
                            { 0,-1 },//向左走 
                            { -1,0 } };//向上走
        //队列初始化        
        int head = 1,tail=1;    //队列的头和尾后指针
        que[head].x = startx;
        que[head].y = starty;
        que[head].f = 0;
        que[head].s = 0;
        tail++;
        //从起点开始搜索 标记为已经走过
        book[startx][starty] = 1;
    
        int flag = 0;//标记是否到达目标地。
        while (head < tail)   //head和tail范围内表示队列的元素，即队列不为空的时候
        {
            for (int k = 0; k <= 3; ++k)   //枚举四种走法
            {
                int tx = que[head].x + next[k][0];
                int ty = que[head].y + next[k][1];
                if (tx<1 || tx>n || ty<1 || ty>m) //判断是否在迷宫范围内
                    continue;
    
                if (a[tx][ty] == 0 && book[tx][ty] == 0)
                {
                    book[tx][ty] = 1;   //不用还原，不同于DFS每个点进入一次队列
    
                    //将新的点插入队列中  
                    que[tail].x = tx;
                    que[tail].y = ty;
                    que[tail].f = head;//这个节点是head扩展出来的
                    que[tail].s = que[head].s + 1;//这里的步数类似于层数，队列中元素层数不超过1
                    tail++;
                }
                if (tx == p&&ty == q)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1)
                break;
            head++;//相当于出队操作
        }
        cout << que[tail - 1].s << endl;//此时即为最小步长 可以通过note.f来打印出路径
    
    }

**DFS BFS实例**  
例1：解救炸弹人，输入一个n 行 m列的地图其中\#表示城墙，G表示敌人，.表示空地，试问在何处安放炸弹可以炸死最多的敌人，一个炸弹可以炸死一行一列的敌人（遇到城墙不可以越过）。  
如下输入实例：

13 13 3 3 //地图大小以及起始位置
    #############
    #GG.GGG#GGG.#
    ###.#G#G#G#G#
    #.......#..G#
    #G#.###.#G#G#
    #GG.GGG.#.GG#
    #G#.#G#.#.#.#
    ##G...G.....#
    #G#.#G###.#G#
    #...G#GGG.GG#
    #G#.#G#G#.#G#
    #GG.GGG#G.GG#
    #############

解法1：采用BFS判断，可以到达的空地，并且统计每个空地上安放炸弹时可以炸死的敌人数目，代码如下：

#include<iostream>
    
    using namespace std;
    
    struct note
    {
        int x;
        int y;
    };
    
    char a[20][20];  //用来存储地图
    
    int getnum(int x, int y) //统计可以炸毁多少个敌人
    {
        int i, j, sum = 0;
        //向右统计
        i = x, j = y;
        while (a[i][j]!='#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            j++;
        }
        //向左统计
        i = x, j = y;
        while (a[i][j] != '#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            j--;
        }
        //向下统计
        i = x, j = y;
        while (a[i][j] != '#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            i++;
        }
        //向上统计
        i = x, j = y;
        while (a[i][j] != '#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            i--;
        }
        return sum;
    }
    int main()
    {
        struct note que[401];// 假设地图大小不超过20*20，扩展队列不会超过401
        int head, tail;//队列的头和尾
        int book[20][20] = {
       0};//用来标记当前点是否走过
        int next[4][2] = { {
       0,1},{
       0,-1},{
       1,0},{-1,0} };//可以走的四个方向
        int sum, max = 0, mx, my;//记录最大可以炸死的敌人个数，和放置炸弹的坐标
        int n, m, startx, starty; //地图的大小行数和列数 以及起使位置
        cin >> n >> m >> startx >> starty;
    
        for (int i = 0; i <= n - 1; ++i)   //存入地图
            for (int j = 0; j <= m - 1; ++j)
                cin >> a[i][j];
    
        //起点入队
        head = 1, tail = 1;
        que[head].x = startx;
        que[head].y = starty;
        tail++;
        book[startx][starty] = 1;
        max = getnum(startx, starty);
        mx = startx, my = starty;
        //遍历整个图
        while (head<tail)
        {
            int tx, ty;
            for (int k = 0; k < 4; ++k) //枚举四个方向
            {
                tx=que[head].x + next[k][0];
                ty=que[head].y + next[k][1];
                if (tx<0 || tx>n - 1 || ty<0 || ty>m - 1)  //不合法 旧尝试下一种情况
                    continue;
    
                if (a[tx][ty] == '.'&&book[tx][ty] == 0) //是空地并且没有走过
                {
                    book[tx][ty] = 1;
                    que[tail].x = tx;   //入队
                    que[tail].y = ty;
                    tail++;
    
                    sum = getnum(tx, ty);//统计当前点放置炸弹可以炸死多少敌人
                    if (sum > max)    //更新当前最大值以及放置炸弹的位置
                    {
                        max = sum;
                        mx = tx;
                        my = ty;
                    }
                }
            }
            head++;//  出队
        }
        cout << "将炸弹放置在" << mx << " " << my << "可以消灭" << max << "个敌人";
        system("pause");
    }

解法2：采用DFS判断每一个点，过程如下：（注意这里遍历到每个点就可以，所以不用回溯）

#include<iostream>
    
    using namespace std;
    
    char a[20][20];  //用来存储地图
    int book[20][20];//用来标记当前点是否走过
    int sum, max, mx, my;//记录最大可以炸死的敌人个数，和放置炸弹的坐标
    int n, m, startx, starty; //地图的大小行数和列数 以及起使位置
    
    int getnum(int x, int y) //统计可以炸毁多少个敌人
    {
        int i, j, sum = 0;
        //向右统计
        i = x, j = y;
        while (a[i][j] != '#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            j++;
        }
        //向左统计
        i = x, j = y;
        while (a[i][j] != '#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            j--;
        }
        //向下统计
        i = x, j = y;
        while (a[i][j] != '#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            i++;
        }
        //向上统计
        i = x, j = y;
        while (a[i][j] != '#')//不是墙就可以继续
        {
            if (a[i][j] == 'G')
                sum++;
            i--;
        }
        return sum;
    }
    
    void dfs(int x, int y)
    {
        int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
        sum = getnum(x, y);//统计当前点放置炸弹可以炸死多少敌人
        if (sum > max)    //更新当前最大值以及放置炸弹的位置
        {
            max = sum;
            mx = x;
            my = y;
        }
        for (int k = 0; k < 4; ++k) //枚举四个方向
        {
            int tx = x + next[k][0];
            int ty = y + next[k][1];
            if (tx<0 || tx>n - 1 || ty<0 || ty>m - 1)  //不合法 旧尝试下一种情况
                continue;
    
            if (a[tx][ty] == '.'&&book[tx][ty] == 0) //是空地并且没有走过
            {
                book[tx][ty] = 1;                    //只是判断每个点，不用回溯
                dfs(tx, ty);
            }
        }
    }
    int main()
    {
        cin >> n >> m >> startx >> starty;
        for (int i = 0; i <= n - 1; ++i)   //存入地图
            for (int j = 0; j <= m - 1; ++j)
                cin >> a[i][j];
        dfs(startx, starty);
        cout << "将炸弹放置在" << mx << " " << my << "可以消灭" << max << "个敌人";
        system("pause");
    }

例2：宝岛探险，给出一幅n行m列的地图，其中0表示海洋，1到9表示陆地，求独立的岛屿个数。（即是求一个图中，独立的子图的个数）  
输入示例：

10 10 
    1 2 1 0 0 0 0 0 2 3
    3 0 2 0 1 2 1 0 1 2
    4 0 1 0 1 2 3 2 0 1
    3 2 0 0 0 1 2 4 0 0
    0 0 0 0 0 0 1 5 3 0
    0 1 2 1 0 1 5 4 3 0
    0 1 2 3 1 3 6 2 1 0
    0 0 3 4 8 9 7 5 0 0
    0 0 0 3 7 8 6 0 1 2
    0 0 0 0 0 0 0 0 1 0

解法1：BFS解法，对岛屿进行着色，（觉得采用DFS比较好）

#include<iostream>
    
    using namespace std;
    
    int a[51][51]; //存储地图
    int book[51][51]; //标记是否走过
    int n, m;    //地图大小
    struct note
    {
        int x;
        int y;
    };
    
    int main()
    {
        int color = 0;//对每个岛屿着色
        struct note que[2501]; //扩展队列 地图大小为50*50 扩展队列不会超过2501
        int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)  //读入地图
            for (int j = 1; j <= m; ++j)
                cin >> a[i][j];
    
        for (int i = 1; i <= n; ++i)                     //对每一个非0的点进行BFS
        {
            for (int j = 1; j <= m; ++j)
            {
                if (a[i][j] > 0)
                {
                    --color;
                    a[i][j] = color;    //进行染色
                    int head = 1, tail = 1;      //入队
                    que[head].x = i;
                    que[head].y = j;
                    tail++;
                    book[i][j] = 1;
                    while (head<tail)
                    {
                        for (int k = 0; k < 4; ++k)      //遍历四个方向
                        {
                            int tx = que[head].x + next[k][0];
                            int ty = que[head].y + next[k][1];
                            if (tx<1 || tx>n || ty<1 || ty>m)   //判断边界是否满足
                                continue;
    
                            if (a[tx][ty] > 0 && book[tx][ty] == 0)
                            {
                                a[tx][ty] = color;     //入队前进行染色
                                que[tail].x = tx;
                                que[tail].y = ty;
                                tail++;
                                book[tx][ty] = 1;
                            }
                        }
                        head++;
                    }
                }
            }
        }
    
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        cout << "有" << -color << "个小岛";
        system("pause");
    }

解法二：采用DFS，进行着色 （相比于BFS容易实现点）

#include<iostream>
    
    using namespace std;
    
    int a[51][51]; //存储地图
    int book[51][51]; //标记是否走过
    int n, m;    //地图大小
    int color;
    void dfs(int x, int y)
    {
        int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
        a[x][y] = color;
    
        for (int k = 0; k < 4; ++k)      //遍历四个方向
        {
            int tx = x + next[k][0];
            int ty = y + next[k][1];
            if (tx<1 || tx>n || ty<1 || ty>m)   //判断边界是否满足
                continue;
            if (a[tx][ty] > 0 && book[tx][ty] == 0)
            {
                book[tx][ty] = 1;
                dfs(tx, ty);        //不用回溯
            }
        }
    }
    
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)  //读入地图
            for (int j = 1; j <= m; ++j)
                cin >> a[i][j];
    
        for (int i = 1; i <= n; ++i)                     //对每一个非0的点进行BFS
        {
            for (int j = 1; j <= m; ++j)
            {
                if (a[i][j] > 0)
                {
                    color--;
                    dfs(i, j);
                }
            }
        }
    
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        cout << "有" << -color << "个小岛";
        system("pause");
    }

例3：水管工游戏：（题目参考《啊哈算法》。。）  
![这里写图片描述][70]

#include<iostream>
    
    using namespace std;
    int a[51][51];
    int book[51][51], n, m,flag;
    
    struct  note
    {
        int x;
        int y;
    }s[100];
    
    int top = 0;
    void dfs(int x,int y,int front)     //front 代表进水口方向
    {
        if (x == n&&y == m + 1)
        {
            flag = 1;
            for (int i = 1; i <= top; ++i)
                cout << "("<<s[i].x << "," << s[i].y << ")" << " ";
            cout << endl;
            return;
        }
        if (x<1 || x>n || y<1 || y>m)
            return;
    
        if (book[x][y] == 1)
            return;
    
        book[x][y] = 1;
        top++;
        s[top].x = x;
        s[top].y = y;
    
        if (a[x][y] >= 5 && a[x][y] <= 6)   //为直管的情况
        {
            if (front == 1)    //进水口在左边
            {
                dfs(x, y + 1, 1);
            }
    
            if (front == 2)     //进水口在上边
            {
                dfs(x + 1, y, 2);
            }
    
            if (front == 3)     //进水口在右边
            {
                dfs(x, y-1, 3);
            }
    
            if (front == 4)     //进水口在下边边
            {
                dfs(x -1, y, 4);
            }
        }
    
        if (a[x][y] >= 1 && a[x][y] <= 4)     //为弯管的时候
        {
            if (front == 1)    //进水口在左边
            {
                dfs(x+1, y , 2);
                dfs(x-1 , y, 4);
            }
    
            if (front == 2)     //进水口在上边
            {
                dfs(x , y + 1, 1);
                dfs(x, y - 1, 3);
            }
    
            if (front == 3)     //进水口在右边
            {
                dfs(x+1, y , 2);
                dfs(x - 1, y, 4);
            }
    
            if (front == 4)     //进水口在下边
            {
                dfs(x, y + 1, 1);
                dfs(x, y - 1, 3);
            }
        }
        book[x][y] = 0;        //取消标记
        top--;                 //将当前尝试坐标出栈
        return;
    }
    
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> a[i][j];
    
        dfs(1, 1, 1);
        if (flag == 0)
            cout << "impossible" << endl;
    
        system("pause");
    }

[70]: /images/20220515/1b45f5f2685a4297abd5911c05a66114.png