C++ 數(shù)據(jù)結(jié)構(gòu)之水洼的數(shù)量算法

更新時間：2017年06月25日 10:22:40 投稿：lqh

這篇文章主要介紹了C++ 數(shù)據(jù)結(jié)構(gòu)之水洼的數(shù)量算法的相關(guān)資料,需要的朋友可以參考下

C++ 數(shù)據(jù)結(jié)構(gòu)之水洼的數(shù)量算法

題目: 有一個大小為N*M的園子, 雨后起了積水. 八連通的積水被認為是連接在一起的. 請求出園子里總共有多少水洼.

使用深度優(yōu)先搜索(DFS), 在某一處水洼, 從8個方向查找, 直到找到所有連通的積水. 再次指定下一個水洼, 直到?jīng)]有水洼為止.
則所有的深度優(yōu)先搜索的次數(shù), 就是水洼數(shù). 時間復(fù)雜度O(8*M*N)=O(M*N).

代碼:

/* 
 * main.cpp 
 * 
 * Created on: 2014.7.12 
 *本欄目更多精彩內(nèi)容：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

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章:

相關(guān)文章

C++日期類實現(xiàn)的完整操作
C++標(biāo)準(zhǔn)庫沒有提供所謂的日期類型,C++繼承了C語言用于日期和時間操作的結(jié)構(gòu)和函數(shù),這篇文章主要給大家介紹了關(guān)于C++日期類實現(xiàn)的完整操作,文中通過代碼介紹的非常詳細,需要的朋友可以參考下
2024-06-06
貪吃蛇游戲C++命令行版實例代碼
這篇文章主要介紹了貪吃蛇游戲C++命令行版實例代碼,包含了常見的循環(huán)語句及相關(guān)游戲規(guī)則的判定方法,有助于更好的理解游戲設(shè)計原理,需要的朋友可以參考下
2014-09-09
C++指針作為函數(shù)的參數(shù)進行傳遞時需要注意的一些問題
當(dāng)指針作為函數(shù)的參數(shù)進行傳遞的時候，本質(zhì)上還是進行的“值傳遞”，也就是復(fù)制了一個新的指向該地址的指針變量
2013-10-10
c++標(biāo)準(zhǔn)庫讀寫ini文件的實現(xiàn)示例
本文介紹了一個完整的INI文件類的實現(xiàn),包含讀取和寫入操作,通過IniFile.h頭文件和IniFile.cpp實現(xiàn)文件,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2024-10-10
C++與namespace有關(guān)的兩個編譯錯誤的講解
今天小編就為大家分享一篇關(guān)于C++與namespace有關(guān)的兩個編譯錯誤的講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
2019-04-04
OpenCV實現(xiàn)車牌定位(C++)
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)車牌定位，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2020-11-11
C++超詳細講解RTTI和cast運算符的使用
RTTI（Runtime Type Identification）是“運行時類型識別”的意思。C++引入這個機制是為了讓程序在運行時能根據(jù)基類的指針或引用來獲得該指針或引用所指的對象的實際類型，cast強制轉(zhuǎn)換運算符是一種特殊的運算符，它把一種數(shù)據(jù)類型轉(zhuǎn)換為另一種數(shù)據(jù)類型
2022-08-08
Qt實現(xiàn)矩形大小任意縮放的示例代碼
這篇文章主要介紹了Qt如何實現(xiàn)在窗口上繪制任意大小的矩形，并且通過邊角的拖曳按鈕可改變矩形大小，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
2022-06-06
基于Qt+opencv開發(fā)的視頻播放器示例詳解
這篇文章主要為大家介紹了基于Qt+opencv開發(fā)的視頻播放器示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
2023-08-08
C++?STL標(biāo)準(zhǔn)庫之std::list使用介紹及用法詳解
std::list是支持常數(shù)時間從容器任何位置插入和移除元素的容器,下面這篇文章主要給大家介紹了關(guān)于C++?STL標(biāo)準(zhǔn)庫之std::list使用介紹及用法詳解的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
2022-11-11