poj_2386

描述

由于最近的一场雨，农夫john的田地里很多地方流入了水，由一个N*M的矩形表示。每个方格要么有水(W)要么是干的（.）。农夫想要知道他的田地里形成了多少池塘。一个池塘由有水的方块相连，每个方块8连通。

思路

对于每个点，8个方向深搜。

属于同一个池塘的点不必重复搜索，因此可以用一个二维数组存放每个点是否被访问过的状态。(记忆化搜索)

代码

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 using namespace std;

 5

 6

 7 int f[102][102], vis[102][102];

 8 int N, M;

 9

10 void read(int a[102][102],int n,int m)

11 {

12     for (int i = 0; i < n; i++)

13     {

14         char str[105];

15         scanf("%s", str);

16         for (int j = 0; j < m; j++)

17             if (str[j] == 'W')

18                 f[i][j] = 1;

19

20     }

21 }

22

23 void dfs(int i, int j)

24 {

25     if (vis[i][j]||!f[i][j])return;

26     if (i < 0 || i >= N || j < 0 || j >= M)return;

27

28     vis[i][j] = 1;

29

30     dfs(i - 1, j - 1);

31     dfs(i - 1, j);

32     dfs(i - 1, j + 1);

33     dfs(i, j - 1);

34     dfs(i, j + 1);

35     dfs(i + 1, j - 1);

36     dfs(i + 1, j);

37     dfs(i + 1, j + 1);

38

39 }

40

41 int main()

42 {

43     //freopen("C:\\Users\\zgwng\\Desktop\\1852.txt", "r", stdin);

44     scanf("%d %d", &N, &M);

45

46     memset(f, 0, sizeof(f));

47     memset(vis, 0, sizeof(vis));

48     int pound = 0;

49

50     read(f, N, M);

51

52     for(int i=0;i<N;i++)

53         for (int j = 0; j < M; j++)

54         {

55             if (f[i][j] && !vis[i][j])

56             {

57                 pound++;

58                 dfs(i, j);

59             }

60         }

61

62     cout << pound << endl;

63

64     return 0;

65

66 }

巴特西

poj_2386_dfs

描述

思路

代码

最新文章

热门文章