7-16 山

Drizzle 前往山地统计大山的数目，现在收到这片区域的地图，地图中用0（平地）和1（山峰）绘制而成，请你帮忙计算其中的大山数目
山总是被平地四面包围着，每一座山只能在水平或垂直方向上连接相邻的山峰而形成。一座山峰四面被平地包围，这个山峰也算一个大山
另外，你可以假设地图的四面都被平地包围着。

要求:

输入：第一行输入M,N分别表示地图的行列，接下来M行每行输入N个数字表示地图
输出：输出一个整数表示大山的数目

示例:

输入：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出：

3

范围:

对于 5% 的数据：M，N ≤ 10
对于 100% 的数据：M，N ≤ 2000

代码长度限制

16 KB

时间限制

1000 ms

内存限制

256 MB

栈限制

8192 KB

#include <stdio.h>
int m, n, cnt;
int A[2001][2001];
void dfs(int A[2001][2001], int i, int j)
{
    if (i < 0 || j < 0 || i == m || j == n || A[i][j] == 0)
        return;
    A[i][j] = 0;
    dfs(A, i + 1, j);
    dfs(A, i - 1, j);
    dfs(A, i, j + 1);
    dfs(A, i, j - 1);
}
int main()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &A[i][j]);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
        {
            if (A[i][j] == 1)
            {
                cnt++;
                dfs(A, i, j);
            }
        }
    printf("%d", cnt);
    return 0;
}