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

发布时间：2020-12-16 05:08:12 所属栏目：百科来源：网络整理

导读：C++ 数据结构之水洼的数量算法题目: 有一个大小为N*M的园子,雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼. 使用深度优先搜索(DFS),在某一处水洼,从8个方向查找,直到找到所有连通的积水. 再次指定下一个水洼,直到没有水洼为

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 = %dn",res); 
  } 
}; 
   
   
int main(void) 
{ 
  Program P; 
  P.solve(); 
  return 0; 
}

输出:

result = 3

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!