BDZNH
0%

Lake Counting

Posted on Edited on
Symbols count in article: Reading time ≈ NaN:aN

Lake Couting

今天看到一个挺有意思的题目，拿出来分享一下。

题目所体现的算法思想为“深度优先搜索”(实在想知道这是神马的，百度一下)

这里给出简单的解释：深度优先搜索从最开始的状态出发，遍历所有可以达到的状态。由此可以对所有的状态进行操作，或者列举出所有的状态。

题目：

有一个大小为N x M 的园子，雨后积满了水。八联通的积水被认为是连接在一起的。请求出这个园子里总共有多少水洼？(八联通指的是下图中相对 w 的 * 的部分)

1
2
3
***
www
***

数据限制：

N<100,m<100

输入数据:

1
2
3
4
5
6
7
8
9
10
11
10 12
w........ww.
.www.....www
....ww...ww.
.........ww.
.........w..
..w......w..
.w.w.....ww.
w.w.w.....w.
.w.w.....w..
..w......ww.

答案：

3

源代码

下面是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstdio>
using namespace std;//C++特有的命名空间，换为C的话，要去掉这行，并且改变头文件
int n,m;//定义全局变量，n为行数，m为列数；
char field[101][101];
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;//向x方向移动dx，向y方向移动dy。
            //判断(nx，ny)是不是在园子范围内，并判断是否有积水
            if(0<=nx&&nx>n&&0<=ny&&ny<m&&field[nx][ny]=='w')
            {
                dfs(nx,ny);//这儿是递归用法，仔细想想
            }
        }
    }
    return ;//这行是可以省略的，因为当前所在函数是void型。
}
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);//从有水(w)的地方开始搜索
                res++;
            }
        }
    }
    printf("%d\n",res);
}
int main()
{
    scanf("%d%d",&n,&m);
    int i=0,j=0;
    for( ; i<n ; i++ )
    {
        for( ; j<m ; j++ )
        {
            scanf("%c",&field[i][j]);
        }
    }
    solve();
    return 0;
}

其实，在windows系统下主函数中的

1
2
3
4
5
6
7
for( ; i<n ; i++ )
{
    for( ; j<m ; j++ )
    {
        scanf("%c",&field[i][j]);
    }
}

也可以改写成

1
2
3
4
for( ;i<n ;i++)
{
	gets(field[i]);
}

或者

1
2
3
4
for( ; i<n ; i++)
{
	scanf("%s",field[i]);
}

来减少一些输入，但是要注意gets函数在linux系统下是不允许使用的(有风险)。
“深度优先搜索”的信息，这种概念行性的东西,诸位还是百度吧，我说不清楚。