P1498 南蛮图腾(递归)用C语言写一份
时间: 2023-12-29 12:18:51 浏览: 30
好的,以下是用 C 语言实现的递归版代码:
```c
#include <stdio.h>
#define MAXN 105
int n, m, ans = 0, len = 0;
int a[MAXN][MAXN], vis[MAXN][MAXN];
void dfs(int x, int y) {
vis[x][y] = 1;
len++;
if (x > 1 && !vis[x - 1][y] && a[x - 1][y]) {
dfs(x - 1, y); // 向上搜索
}
if (y > 1 && !vis[x][y - 1] && a[x][y - 1]) {
dfs(x, y - 1); // 向左搜索
}
if (x < n && !vis[x + 1][y] && a[x + 1][y]) {
dfs(x + 1, y); // 向下搜索
}
if (y < m && !vis[x][y + 1] && a[x][y + 1]) {
dfs(x, y + 1); // 向右搜索
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!vis[i][j] && a[i][j]) {
len = 0;
dfs(i, j);
ans = ans > len ? ans : len;
}
}
}
printf("%d\n", ans);
return 0;
}
```
这里使用了一个 `dfs` 函数来搜索连通块,参数 `x` 表示当前搜索的行号,参数 `y` 表示当前搜索的列号。在 `dfs` 函数中,首先标记当前位置已经访问过,并将计数器 `len` 加一。然后分别向上、向左、向下、向右四个方向进行搜索,如果当前位置没有访问过且是连通块的一部分,则继续递归搜索。最后返回时,`len` 就是当前连通块的大小。在主函数中,枚举每个位置,如果该位置没有访问过且是连通块的一部分,则调用 `dfs` 函数进行搜索,并更新最大连通块大小。