`

玩转深度优先搜索算法

阅读更多

小时候玩游戏,有个BOMB人的游戏,把BOMB放在一个空地上,将怪兽炸死,如图:

 

BOMB的威力只要不碰到墙壁,可以无限延长。那么我们应该把BOMB放哪里可以炸死最多的怪兽呢?

 

这个问题貌似很简单,一个一个地方试下不就知道了吗?是啊,那我们用代码来试下。

 

将图象转成字符,用#表示墙,用G表示怪兽,用.表示空地,最后得到的字符为:

#############

#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#

#############

那我只要把所有的空地试下就知道哪里放BOMB最好了。

int main()
{
    char a[20][20];
    int i, j, sum , map, p, q = 0;
    int n, m, x, y; //m表示多少行字符,n表示多少列字符
    scanf("%d %d", &n, &m);

    for(i = 0; i <= n - 1; i++)
    {
        scanf("%s", a[i]);
    }

    for (i = 0; i <= n - 1; i++)
    {
        for (j = 0; j <= m - 1; j++)
        {
            //判断当前所在位置是不是平地,是平地才可以放BOMB
            if(a[i][j] != '.')
            {
                continue;
            }

            //当前可以炸0个怪兽
            sum = 0;

            x = i;
            y = j;

            //向上扩展计算消灭的怪兽数
            while(a[x][y] != '#')
            {

                if(a[x][y] == 'G')sum++;
                x--;
            }

            x = i;
            y = j;

            //向下扩展计算消灭的怪兽数
            while(a[x][y] != '#')
            {

                if(a[x][y] == 'G')sum++;
                x++;
            }

            x = i;
            y = j;

            //向左扩展计算消灭的怪兽数
            while(a[x][y] != '#')
            {

                if(a[x][y] == 'G')sum++;
                y--;
            }

            x = i;
            y = j;

            //向右扩展计算消灭的怪兽数
            while(a[x][y] != '#')
            {

                if(a[x][y] == 'G')sum++;
                y++;
            }

            //如果消灭的怪兽大于map,则更新map,并记住所在的坐标
            if(sum > map)
            {
                map = sum;
                p = i;
                q = j;
            }
        }
    }

    printf("将BOMB放在(%d,%d)处,可以消灭最多%d怪兽只\n", p, q, map);
    getchar();
    getchar();
    return 0;
}

 打印结果为:将BOMB放在(1,11)处,可以消灭最多11怪兽只。这种算法为枚举,

 

好像有点不对劲啊,小人根本到不了(1,11),所以那里根本不放了BOMB。所以说我们不能将所有的空地都计算进去,需要将到不了的空地排除。这里该深度优先算法出场了(当然还有其它算法可以解决)。

 

走过迷宫的都知道,我们会沿一条走到头,死路时就回头,回到上一个岔路口,已经确定了一条死路,我们就走另一条路,又是死路,我们就再回到岔路口,两条都是死路了,就回到上上个岔路口,依此循环。

 

这个问题就像小人在走迷宫,直到所有的空地都被小人走过为此。我们用递归来实现这个逻辑:

char a[20][21];
int book[20][20];//标记某个点是否被走过
int max, mx, my, n, m;

//计算当前空地可以炸死的怪兽
int getSum(int i, int j)
{
    int sum, x, y;
    //当前可以炸0个怪兽
    sum = 0;

    x = i;
    y = j;

    //向上扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        x--;
    }

    x = i;
    y = j;

    //向下扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        x++;
    }

    x = i;
    y = j;

    //向左扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        y--;
    }

    x = i;
    y = j;

    //向右扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        y++;
    }

    return sum;
}


void dfs(int x, int y)
{
    //定义上下左右走动时x,y轴的变化
    int next[4][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}};

    int k, sum, tx, ty;

    sum = getSum(x, y);

    if(sum > max)
    {
        max = sum;
        mx = x;
        my = y;
    }

    for(k = 0; k <= 3; k++)
    {
        tx = x + next[k][0];
        ty = y + next[k][1];

        if(tx < 0 || tx > n - 1 || ty < 0 || ty > n - 1)continue;

        if(a[tx][ty] == '.' && book[tx][ty] == 0)
        {
            book[tx][ty] = 1;//标记走过这个空地了
            dfs(tx, ty);//走向下一个空地
        }
    }
    return ;
}

int main()
{
    int i, startx, starty;

    scanf("%d %d %d %d", &n, &m, &startx, &starty);

    for(i = 0; i <= n - 1; i++)
    {
        scanf("%s", a[i]);
    }

    book[startx][starty] = 1;
    mx = startx;
    my = starty;
    max = getSum(startx, starty);

    dfs(startx, starty);
    printf("将BOMB放置在(%d,%d),最多可以消灭%d个怪兽\n", mx, my, max );
    return 0;
}

 得到结果:将BOMB放置在(7,11),最多可以消灭10个怪兽。

 

 

我再用“栈”来实现:

char a[20][21];

//栈的节点
struct  note
{
    int x;
    int y;
};

//获取当前空地能消灭的怪兽数
int getSum(int i, int j)
{
    int sum, x, y;
    //当前可以炸0个怪兽
    sum = 0;

    x = i;
    y = j;

    //向上扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        x--;
    }

    x = i;
    y = j;

    //向下扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        x++;
    }

    x = i;
    y = j;

    //向左扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        y--;
    }

    x = i;
    y = j;

    //向右扩展计算消灭的怪兽数
    while(a[x][y] != '#')
    {

        if(a[x][y] == 'G')sum++;
        y++;
    }

    return sum;
}


int main()
{
    //初始化一个栈
    struct note que[401];
    int book[20][20];
    int n,m,mx,my,max,top=0, i, startx, starty;

    scanf("%d %d %d %d", &n, &m, &startx, &starty);

    for(i = 0; i <= n - 1; i++)
    {
        scanf("%s", a[i]);
    }

    book[startx][starty] = 1;
    mx = startx;
    my = starty;
    //当起始点加入到栈中
    top++;
    que[top].x = startx;
    que[top].y = starty;
    max = getSum(startx, starty);

    int next[4][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}};

    int k, sum, tx, ty;
    
    //直到栈空了
    while(top != 0)
    {
        sum = getSum(que[top].x, que[top].y);

        if(sum > max)
        {
            max = sum;
            mx = que[top].x;
            my = que[top].y;
        }

        for(k = 0; k <= 3; k++)
        {
            tx = que[top].x + next[k][0];
            ty = que[top].y + next[k][1];

            if(tx < 0 || tx > n - 1 || ty < 0 || ty > n - 1)continue;

            if(a[tx][ty] == '.' && book[tx][ty] == 0)
            {
                book[tx][ty] = 1;
                top++;
                que[top].x = tx;
                que[top].y = ty;
                break;
            }
            //这句很关键,一个空地上下左右都试走过后,将此空地移除栈
            if(k == 3)top--;
        }
    }
    printf("将BOMB放置在(%d,%d),最多可以消灭%d个怪兽\n", mx, my, max );
    return 0;
}

 得到的结果是一样的。

 

这套算法应用十分广泛,可以解决很多问题。作为一名码农还是非常有必要学习一下的,与这对应的还有“广度优先搜索算法”.

  • 大小: 16.8 KB
2
0
分享到:
评论
2 楼 home198979 2016-08-03  
q315506754 写道
还是佩服写c的

用其它语言一样可以实现的
1 楼 q315506754 2016-08-02  
还是佩服写c的

相关推荐

    算法实战论坛

    搜索算法如二分查找、深度优先搜索、广度优先搜索则在数据检索中发挥关键作用。 2. **数据结构**:高效算法往往离不开合理的数据结构支持,如数组、链表、树、堆、图等。这些数据结构在处理数据时有不同的时间和...

    玩转算法leetcode.docx

    搜索算法主要包括深度优先搜索(DFS)和广度优先搜索(BFS)。DFS适合于遍历或搜索树或图,常用于解迷宫问题;BFS通常用于找到图中两个节点之间的最短路径,例如在网络路由中。 动态规划(DP)是一种通过将问题分解为子...

    玩转数据结构.zip........

    图的遍历算法有深度优先搜索(DFS)和广度优先搜索(BFS)。 9. **排序算法**:排序是指将一组数据按特定顺序排列的过程。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。不同的...

    基于Python的玩转小迷宫.zip

    在计算机科学中,解决此类问题的常见算法有深度优先搜索(DFS)、广度优先搜索(BFS)以及A*搜索算法等。这些算法都需要对图或树结构进行遍历,以找到最优路径。 1. **深度优先搜索(DFS)**:DFS是一种递归的搜索...

    十大算法精讲资料.rar

    4. **栈**:栈是一种后进先出(LIFO)的数据结构,常用于实现函数调用、表达式求值(如逆波兰表示法)以及深度优先搜索等。栈的基本操作有压栈、弹栈和查看栈顶元素。 5. **队列**:队列是先进先出(FIFO)的数据...

    啊哈算法哈磊第六节水管工游戏问题DFS算法(java)

    资源描述:本资源深入探讨了《啊哈算法》第六章节的趣味挑战——“水管工游戏问题”,通过Java语言实现了DFS(深度优先搜索)算法来解决这一经典管道连接谜题。在本资源中,哈磊老师巧妙地将DFS算法应用于水管工游戏...

    啊哈算法哈磊图的遍历(DFS算法)-Java实现

    资源描述:本资源深入探讨了《啊哈算法》第六章节的趣味挑战——“水管工游戏问题”,通过Java语言实现了DFS(深度优先搜索)算法来解决这一经典管道连接谜题。在本资源中,哈磊老师巧妙地将DFS算法应用于水管工游戏...

    算法面试专题课(Java版),Google面试官带你高质量刷题视频教程

    1. **基础算法**:包括排序(如快速排序、归并排序、堆排序等)、搜索(如二分查找、广度优先搜索、深度优先搜索)以及图论的基础知识,这些都是面试中的常考内容。 2. **数据结构**:深入理解链表、栈、队列、树...

    扩展矩阵leetcode-imooc_algorithm_graph:慕课网《玩转算法系列--图论精讲》笔记及Golang代码实现

    慕课网《玩转算法系列--图论精讲》笔记 明确变量的语义!!! 忘记的概念 图的基本表示 联通分量(2-2 8:13) 树是一种无环图(2-2 10:26) 联通的无环图是树(2-2 11:27) 联通图的生成树包含所有顶点(2-2 12:38)...

    连连看消除算法

    在设计连连看消除算法时,我们通常会采用深度优先搜索(DFS)或广度优先搜索(BFS)策略。这两种算法都是图遍历的经典方法,适用于解决棋盘上的路径查找问题。 1. **深度优先搜索(DFS)**:DFS从一个棋子出发,...

    玩转数据结构

    图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS),是解决许多图问题的基础。 哈希表是一种能快速查找和存储数据的数据结构,通过哈希函数将数据映射到固定大小的数组中。理想的哈希函数可以使查找、插入...

    小游戏连连看的详细算法

    - 为了找到可消除的匹配对,我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法。 - DFS可以从一个方块开始,沿着可能的路径尝试找到另一个匹配的方块,如果找到则返回true,否则回溯。 - BFS则使用队列...

    包含自动求解算法程序的完美版JavaScript拼图游戏

    这种算法通常基于搜索策略,如深度优先搜索(DFS)或广度优先搜索(BFS),或者采用A*搜索算法,结合启发式函数来指导搜索,确保在有限计算资源下找到最佳解决方案。 在JavaScript中实现这样的算法,需要掌握基本的...

    玩转数据结构(高清视频教程).rar

    图的遍历算法有深度优先搜索(DFS)和广度优先搜索(BFS),它们在解决最短路径、最小生成树等问题时非常有用。 此外,哈希表提供了一种快速查找的方法,通过哈希函数将键映射到数组的索引,实现近乎常数时间的查找、...

    基础入门连连看算法

    4. 广度优先搜索(BFS)或深度优先搜索(DFS): 在检查两个图案是否能连通时,可以采用搜索算法。BFS通常用于寻找最短路径,而DFS可以用于检查是否存在合法路径。在连连看的实现中,BFS可能是更好的选择,因为它...

    seashells:玩转“贝壳的算法之美”

    在"贝壳的算法之美"中,作者可能讲解了排序算法(如快速排序、归并排序)、搜索算法(如二分查找、深度优先搜索)、图论问题(如最短路径算法Dijkstra或Floyd-Warshall)以及数据结构(如链表、树、哈希表)等基础...

    纯Python代码玩转小迷宫.zip

    常见的算法有深度优先搜索(DFS)和广度优先搜索(BFS)。DFS通常使用栈来实现,而BFS则用队列。这两种算法都可以找到从起点到终点的路径,但BFS通常能找到最短路径。此外,可能还会涉及回溯法,当搜索到死路时,回...

    纯python代码玩转小迷宫

    例如,深度优先搜索(DFS)或者Prim's算法都是常见的生成方法。这里我们以DFS为例,从一个随机起点开始,每次选择一个未访问的相邻节点,并将其标记为已访问,直到所有可到达的节点都被标记。 2. **打印迷宫**:...

Global site tag (gtag.js) - Google Analytics