C++ 數據結構之水洼的數量算法

2020-01-26 14:03:31

字體：大中小

來源：轉載

供稿：網友

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; }

輸出: