Lake Counting(POJ-2386)

题目链接http://poj.org/problem?id=2386

题目大意: 计算出相连的'W'有多少块

所需算法: 深度优先搜索(DFS)

主要思路: 从任意的W开始,不停地把邻接的8个点用'.'代替。一次DFS后与一开始的W连接的所有W就被换成了'.',计数加1,继续DFS直到图中无W。

算法复杂度:O(8*N*M) = O(N*M)

代码如下

 1 #include <cstdio>
 2 
 3 const int MAX_N = 100, MAX_M = 100;
 4 char field[MAX_N][MAX_M+1];
 5 int n, m;
 6 
 7 void DFS(int x, int y);
 8 
 9 int main()
10 {
11     int num = 0;
12 
13     scanf("%d %d", &n, &m);
14     for (int i = 0; i < n; i++)
15         scanf("%s", field[i]);
16 
17     for (int i = 0; i < n; i++)
18         for (int j = 0; j < m; j++)
19             if (field[i][j] == 'W') {//从有W的地方DFS
20                 DFS(i, j);
21                 num++;
22             }
23     printf("%d\n", num);
24     return 0;
25 }
26 
27 void DFS(int x, int y)
28 {
29     //遍历8个方向
30     for (int dx = -1; dx <= 1; dx++)
31         for (int dy = -1; dy <= 1; dy++) {
32             int nx = x + dx;
33             int ny = y + dy;
34             //判断(nx, ny)是否在园子内且是否有积水
35             if (nx >= 0 && nx < n && ny >=0 && ny < m && field[nx][ny] == 'W') {
36                 field[nx][ny] = '.';
37                 DFS(nx, ny);
38             }
39         }
40 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

数据结构之图

基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间...

2145
来自专栏尾尾部落

[剑指offer] 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

912
来自专栏云霄雨霁

加权无向图----加权无向图的实现

1810
来自专栏向治洪

图算法之bfs、dfs、prim、Dijkstra

概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

5096
来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

3596
来自专栏机器学习与自然语言处理

判断有向图是否有圈

1. 拓扑排序 拓扑排序是对有向无圈图的顶点的一种排序:如果存在一条vi到vj的路径,则vj排在vi后面(因为只要满足这个特性就是拓扑序列,所以它不一定是唯一的...

4228
来自专栏编程理解

数据结构(八):邻接表与邻接矩阵

邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

2143
来自专栏用户画像

5.3.2 深度优先搜索(Depth-First-Search,DFS)

与广度优先搜索不同,深度优先搜索(DFS)类似于树的先序遍历。正如其名称中所暗含的意思一样,这种搜索所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下...

1013
来自专栏数据结构与算法

BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

4706
来自专栏算法与数据结构

数据结构 图

1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

4267

扫码关注云+社区

领取腾讯云代金券