# C-C-plus-plus

**Repository Path**: Aslite/algorithmC

## Basic Information

- **Project Name**: C-C-plus-plus
- **Description**: algorithm about C/C++(topcoder).
- **Primary Language**: C++
- **License**: AFL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-01-22
- **Last Updated**: 2024-01-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# C-C-plus-plus

#### 介绍
algorithm about C/C++(topcoder).
daya#1 dfs

#### 原理思路：
题目意思：给定一个园子，园子中有一些积水洼（用W表示），要求计算园子中一共有多少个积水洼。这里的积水洼是指八连通的积水被认为是连接在一起的。

解题思路：我们可以遍历整个园子，当遇到一个积水洼时，就将它标记为已访问，并使用深度优先搜索（DFS）找到所有与该积水洼相连的积水洼，并将它们全部标记为已访问。最后，我们统计标记为已访问的积水洼的数量，即为园子中总共的积水洼数量。以下是解题的详细步骤：

1，我们从园子的左上角开始，遍历整个园子的每一个格子。
2，当我们遇到一个水洼（用 'W' 表示）时，我们将其标记为已访问，并将水洼数量加一。
3，然后，我们对当前水洼进行深度优先搜索（DFS），寻找所有与当前水洼相连的其他水洼。在DFS的过程中，我们会遍历当前水洼的上、下、左、右以及斜对角的格子，查找是否有未访4，问过的水洼，如果有，我们将其标记为已访问，并对其进行DFS。
我们重复上述步骤，直到我们遍历完整个园子。
5，最后，我们统计标记为已访问的水洼的数量，即为园子中总共的水洼数量。

#### 特技
时间复杂度为 O(rows * cols)，空间复杂度为 O(1)（不考虑输入的空间）。优化版本的思路可以包括使用并查集（Union-Find）数据结构来优化水洼的连接判断，以及使用非递归的深度优先搜索或广度优先搜索等。