lake counting -- DFS 搜索
搜索 -- DFS Counting Lake
2023-09-27 14:28:36 时间
问题
http://poj.org/problem?id=2386
Description
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.
Given a diagram of Farmer John's field, determine how many ponds he has.Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.Output
* Line 1: The number of ponds in Farmer John's field.Sample Input
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.Sample Output
3Hint
OUTPUT DETAILS:
There are three ponds: one in the upper left, one in the lower left,and one along the right side.
思路
对于每一个water ponds, 需要使用dfs 搜索其边界。
使用二维遍历, 当找到第一个为w的square,此点为一个ponds的部分, 从此点开始dfs搜索water ponds所有W块和边界。
Code
#include <bits/stdc++.h> #include <vector> #include <algorithm> #include <deque> #include <queue> #include <string> #include <set> using namespace std; /* http://poj.org/problem?id=2386 */ bool wfields[102][102] = {{false}}; bool visited[102][102] = {{false}}; int n, m; void dfs(int i, int j) { if (i < 1 || i > n ) { // cout << "i is out of bound. i=" << i << endl; return; } if (j < 1 || j > m) { // cout << "j is out of bound. j=" << j << endl; return; } if (visited[i][j] == true) { return ; } else { visited[i][j] = true; } if (wfields[i][j] == false) { // cout << "water fields is false." << endl; return; } for (int diff_i = -1; diff_i <= 1; diff_i++) { for (int diff_j = -1; diff_j <= 1; diff_j++) { dfs(i + diff_i, j + diff_j); } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { string temp; cin >> temp; for (int j = 1; j <= m; j++) { if (temp[j - 1] == 'W') { wfields[i][j] = true; } else { wfields[i][j] = false; } visited[i][j] = false; } } int count = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (wfields[i][j] == true && visited[i][j] == false) { count ++; dfs(i, j); } } } cout << count << endl; }
相关文章
- C#winform抓取百度,Google搜索关键词结果
- Elasticsearch-数据的存储、搜索(干货)
- 【BZOJ4428】[Nwerc2015]Debugging调试 记忆化搜索+分块
- Java实现 二叉搜索树算法(BST)
- 个性化搜索召回模型设计--训练部分
- 开放式测试搜索不到应用怎么办
- UVa 1252 Twenty Questions (状压DP+记忆化搜索)
- 期刊模板搜索网址
- 《剑指offer》-- 序列化二叉树、二叉搜索树的第k个节点、数据流中的中位数、滑动窗口的最大值
- 【蓝桥杯Java组】送你一个不会出错的二分搜索模板
- 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索
- Python数据结构与算法(5)--搜索和排序
- [LeetCode] 1305. All Elements in Two Binary Search Trees 两棵二叉搜索树中的所有元素
- [LeetCode] Find Mode in Binary Search Tree 找二分搜索数的众数
- 就是这么迅猛的实现搜索需求--转