欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

啊哈算法(4)—万能的搜索

程序员文章站 2022-06-11 11:13:39
...

深度优先搜索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:水管工游戏:(题目参考《啊哈算法》。。)
啊哈算法(4)—万能的搜索

#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");
}