欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間：2017年06月25日 10:22:40   投稿：lqh  
這篇文章主要介紹了C++ 數(shù)據(jù)結(jié)構(gòu)之水洼的數(shù)量算法的相關(guān)資料,需要的朋友可以參考下

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

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

使用深度優(yōu)先搜索(DFS), 在某一處水洼, 從8個(gè)方向查找, 直到找到所有連通的積水. 再次指定下一個(gè)水洼, 直到?jīng)]有水洼為止.
則所有的深度優(yōu)先搜索的次數(shù), 就是水洼數(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

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

相關(guān)文章

  • C++如何調(diào)用已經(jīng)寫好的C接口

    C++如何調(diào)用已經(jīng)寫好的C接口

    如何在C++代碼中調(diào)用寫好的C接口?你可能會(huì)奇怪，C++不是兼容C嗎?直接調(diào)用不就可以了，那么我們來(lái)測(cè)試一下，先看看C++如何調(diào)用C代碼接口的,需要的朋友可以參考一下
    2021-10-10
  • C++?左值引用與一級(jí)指針示例詳解

    C++?左值引用與一級(jí)指針示例詳解

    這篇文章主要介紹了C++?左值引用與一級(jí)指針,本文給大家介紹了C++?(左值)引用和指針簡(jiǎn)介，結(jié)合示例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
    2022-09-09
  • C++實(shí)現(xiàn)線程池的簡(jiǎn)單方法示例

    C++實(shí)現(xiàn)線程池的簡(jiǎn)單方法示例

    這篇文章主要給大家介紹了關(guān)于C++實(shí)現(xiàn)線程池的簡(jiǎn)單方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-05-05
  • 深入學(xué)習(xí)C++中的函數(shù)概念

    深入學(xué)習(xí)C++中的函數(shù)概念

    這篇文章主要介紹了C++中的函數(shù)概念,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2015-09-09
  • C++探索構(gòu)造函數(shù)私有化會(huì)產(chǎn)生什么結(jié)果

    C++探索構(gòu)造函數(shù)私有化會(huì)產(chǎn)生什么結(jié)果

    C++的構(gòu)造函數(shù)的作?：初始化類對(duì)象的數(shù)據(jù)成員。即類的對(duì)象被創(chuàng)建的時(shí)候，編譯系統(tǒng)對(duì)該對(duì)象分配內(nèi)存空間，并?動(dòng)調(diào)?構(gòu)造函數(shù)，完成類成員的初始化。構(gòu)造函數(shù)的特點(diǎn)：以類名作為函數(shù)名，?返回類型
    2022-05-05
  • C++?STL之string的模擬實(shí)現(xiàn)實(shí)例代碼

    C++?STL之string的模擬實(shí)現(xiàn)實(shí)例代碼

    C++中有命名空間的存在,我們只需把我們的代碼封到自定義的命名空間即可,下面這篇文章主要給大家介紹了關(guān)于C++?STL之string的模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下
    2023-01-01
  • C語(yǔ)言刪除輸入字符串中的空格示例代碼

    C語(yǔ)言刪除輸入字符串中的空格示例代碼

    最近工作中遇到了需求,要?jiǎng)h除字符串中的所有空格,就要篩選出空格字符,這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言刪除輸入字符串中的空格的相關(guān)資料,需要的朋友可以參考下
    2022-12-12
  • C++超詳細(xì)講解auto與nullptr的使用

    C++超詳細(xì)講解auto與nullptr的使用

    C++11提供了nullptr用來(lái)取代0或者NULL。在C++11之前，使用NULL為空指針賦初值，但NULL其實(shí)就是0，這時(shí)會(huì)把NULL當(dāng)成0來(lái)用；在C++11中，我們?cè)诼暶饕粋€(gè)變量或?qū)ο?，指定它的類型時(shí)，可以不使用變量本身的類型而使用auto替代
    2022-05-05
  • 輸出1000以內(nèi)的素?cái)?shù)的算法(實(shí)例代碼)

    輸出1000以內(nèi)的素?cái)?shù)的算法(實(shí)例代碼)

    本篇文章是對(duì)輸出1000以內(nèi)的素?cái)?shù)的算法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
    2013-05-05
  • Qt使用TabWidget實(shí)現(xiàn)多窗體功能

    Qt使用TabWidget實(shí)現(xiàn)多窗體功能

    Qt 是一個(gè)跨平臺(tái)C++圖形界面開(kāi)發(fā)庫(kù),利用Qt可以快速開(kāi)發(fā)跨平臺(tái)窗體應(yīng)用程序,在Qt中我們可以通過(guò)拖拽的方式將不同組件放到指定的位置,本章將重點(diǎn)介紹TabWidget標(biāo)簽組件的常用方法及靈活運(yùn)用,需要的朋友可以參考下
    2023-12-12

最新評(píng)論