微客导航 » 文章资讯 » C++ 数据结构之水洼的数量算法

C++ 数据结构之水洼的数量算法

2024-02-18 01:45:03 202

C++数据结构之水洼的数量算法

题目:有一个大小为N*M的园子,雨后起了积水.八连通的积水被认为是连接在一起的.请求出园子里总共有多少水洼.

使用深度优先搜索(DFS),在某一处水洼,从8个方向查找,直到找到所有连通的积水.再次指定下一个水洼,直到没有水洼为止.
则所有的深度优先搜索的次数,就是水洼数.时间复杂度O(8*M*N)=O(M*N).

代码:

/*
*main.cpp
*
*Createdon:2014.7.12
*本栏目更多精彩内容：http://www.bianceng.cn/Programming/sjjg/
*Author:spike
*/

#include
#include
#include
#include

classProgram{
staticconstintMAX_N=20,MAX_M=20;
intN=10,M=12;
charfield[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."};
voiddfs(intx,inty){
field[x][y]='.';
for(intdx=-1;dx<=1;dx++){
for(intdy=-1;dy<=1;dy++){
intnx=x+dx,ny=y+dy;
if(0<=dx&&nx
输出:


result=3
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

返回顶部
3162201930
czq8825@qq.com

C++ 数据结构之水洼的数量算法

热门推荐

随机推荐