小时候玩游戏,有个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; }
得到的结果是一样的。
这套算法应用十分广泛,可以解决很多问题。作为一名码农还是非常有必要学习一下的,与这对应的还有“广度优先搜索算法”.
相关推荐
搜索算法如二分查找、深度优先搜索、广度优先搜索则在数据检索中发挥关键作用。 2. **数据结构**:高效算法往往离不开合理的数据结构支持,如数组、链表、树、堆、图等。这些数据结构在处理数据时有不同的时间和...
搜索算法主要包括深度优先搜索(DFS)和广度优先搜索(BFS)。DFS适合于遍历或搜索树或图,常用于解迷宫问题;BFS通常用于找到图中两个节点之间的最短路径,例如在网络路由中。 动态规划(DP)是一种通过将问题分解为子...
图的遍历算法有深度优先搜索(DFS)和广度优先搜索(BFS)。 9. **排序算法**:排序是指将一组数据按特定顺序排列的过程。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。不同的...
在计算机科学中,解决此类问题的常见算法有深度优先搜索(DFS)、广度优先搜索(BFS)以及A*搜索算法等。这些算法都需要对图或树结构进行遍历,以找到最优路径。 1. **深度优先搜索(DFS)**:DFS是一种递归的搜索...
4. **栈**:栈是一种后进先出(LIFO)的数据结构,常用于实现函数调用、表达式求值(如逆波兰表示法)以及深度优先搜索等。栈的基本操作有压栈、弹栈和查看栈顶元素。 5. **队列**:队列是先进先出(FIFO)的数据...
资源描述:本资源深入探讨了《啊哈算法》第六章节的趣味挑战——“水管工游戏问题”,通过Java语言实现了DFS(深度优先搜索)算法来解决这一经典管道连接谜题。在本资源中,哈磊老师巧妙地将DFS算法应用于水管工游戏...
资源描述:本资源深入探讨了《啊哈算法》第六章节的趣味挑战——“水管工游戏问题”,通过Java语言实现了DFS(深度优先搜索)算法来解决这一经典管道连接谜题。在本资源中,哈磊老师巧妙地将DFS算法应用于水管工游戏...
1. **基础算法**:包括排序(如快速排序、归并排序、堆排序等)、搜索(如二分查找、广度优先搜索、深度优先搜索)以及图论的基础知识,这些都是面试中的常考内容。 2. **数据结构**:深入理解链表、栈、队列、树...
慕课网《玩转算法系列--图论精讲》笔记 明确变量的语义!!! 忘记的概念 图的基本表示 联通分量(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则使用队列...
这种算法通常基于搜索策略,如深度优先搜索(DFS)或广度优先搜索(BFS),或者采用A*搜索算法,结合启发式函数来指导搜索,确保在有限计算资源下找到最佳解决方案。 在JavaScript中实现这样的算法,需要掌握基本的...
图的遍历算法有深度优先搜索(DFS)和广度优先搜索(BFS),它们在解决最短路径、最小生成树等问题时非常有用。 此外,哈希表提供了一种快速查找的方法,通过哈希函数将键映射到数组的索引,实现近乎常数时间的查找、...
4. 广度优先搜索(BFS)或深度优先搜索(DFS): 在检查两个图案是否能连通时,可以采用搜索算法。BFS通常用于寻找最短路径,而DFS可以用于检查是否存在合法路径。在连连看的实现中,BFS可能是更好的选择,因为它...
在"贝壳的算法之美"中,作者可能讲解了排序算法(如快速排序、归并排序)、搜索算法(如二分查找、深度优先搜索)、图论问题(如最短路径算法Dijkstra或Floyd-Warshall)以及数据结构(如链表、树、哈希表)等基础...
常见的算法有深度优先搜索(DFS)和广度优先搜索(BFS)。DFS通常使用栈来实现,而BFS则用队列。这两种算法都可以找到从起点到终点的路径,但BFS通常能找到最短路径。此外,可能还会涉及回溯法,当搜索到死路时,回...
例如,深度优先搜索(DFS)或者Prim's算法都是常见的生成方法。这里我们以DFS为例,从一个随机起点开始,每次选择一个未访问的相邻节点,并将其标记为已访问,直到所有可到达的节点都被标记。 2. **打印迷宫**:...