题目ID：8014必做题100分
最新提交：
20 分
时间限制: 1000ms
空间限制: 32000kB
题目描述
由于近期的降雨，雨水汇集在田地不同的地方。
我们用一个 N∗MN∗M 的网格图表示，每个网格中有水 1 或是旱地 0，一个网格与其周围的 88 个网格相连，而一组相连的网格视为一个水坑。
请问田地中有多少水坑？
输入格式
第 1 行：两个空格隔开的整数 NN 和 MM。 (1≤N≤100;1≤M≤1001≤N≤100;1≤M≤100)
第 2 行到第 N+1 行：每行 M 个字符，每个字符是 1 或 0，它们表示网格图中的一排。字符之间没有空格。
输出格式
一个整数表示水坑的数量。
样例
Input 1
5 5 10011 10010 11011 01000 11010
Output 1
3
数据范围
1≤N≤100;1≤M≤1001≤N≤100;1≤M≤100
附上代码：
#include <iostream>
using namespace std;
int n, m, ans;
char mapa[105][105];
int vis[105][105];
int record[105][105];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
void dfs(int x, int y) {
if (x == n && y == m) {
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] == 1 || mapa[nx][ny] == '0') {
continue;
}
vis[nx][ny] = 1;
record[nx][ny] = 1;
dfs(nx, ny);
vis[nx][ny] = 0;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mapa[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mapa[i][j] == '1' && record[i][j] != 1) {
dfs(i, j);
ans++;
}
}
}
cout << ans;
return 0;
}