这篇文章给大家分享的是有关C++数据结构之如何实现水洼数量算法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼.
使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止.
则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O(8*M*N)=O(M*N).
代码:
/* * main.cpp * * Created on: 2014.7.12 *本栏目更多精彩内容:http://www.bianceng.cn/Programming/sjjg/ * Author: spike */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> class Program { static const int MAX_N=20, MAX_M=20; int N = 10, M = 12; char field[MAX_N][MAX_M+1] = { "W........WW.", ".WWW.....WWW", "....WW...WW.", ".........WW.", ".........W..", "..W......W..", ".W.W.....WW.", "W.W.W.....W.", ".W.W......W.", "..W.......W."}; void dfs(int x, int y) { field[x][y] = '.'; for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { int nx = x+dx, ny = y+dy; if (0<=dx&&nx<N&&0<=ny&&ny<=M&&field[nx][ny]=='W') dfs(nx, ny); } } return; } public: void solve() { int res=0; for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { if (field[i][j] == 'W') { dfs(i,j); res++; } } } printf("result = %d\n", res); } }; int main(void) { Program P; P.solve(); return 0; }
输出:
result = 3
感谢各位的阅读!关于“C++数据结构之如何实现水洼数量算法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。