E卷-机器人活动区域(100分)

机器人活动区域

问题描述

现有一个机器人，可放置于 的网格中任意位置，每个网格包含一个非负整数编号，当相邻网格的数字编号差值的绝对值小于等于 1 时，机器人可以在网格间移动。

问题： 求机器人可活动的最大范围对应的网格点数目。

说明： 网格左上角坐标为 ，右下角坐标为 ，机器人只能在相邻网格间上下左右移动。

输入格式

第 1 行输入为 和 ， 表示网格的行数， 表示网格的列数。 之后 行表示网格数值，每行 个数值（数值大小用 表示），数值间用单个空格分隔，行首行尾无多余空格。

输出格式

输出 1 行，包含 1 个数字，表示最大活动区域的网格点数目，行首行尾无多余空格。

样例输入

4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4

样例输出

6

样例解释

+---+---+---+---+
| 1 | 2 |*5*| 2 |
+---+---+---+---+
| 2 |*4*|*4*|*5*|
+---+---+---+---+
| 3 |*5*| 7 | 1 |
+---+---+---+---+
| 4 |*6*| 2 | 4 |
+---+---+---+---+

图中标记为 * 的区域，相邻网格差值绝对值都小于等于 1，且为最大区域，对应网格点数目为 6。

数据范围

题解

这道题目本质上是一个图的连通性问题。

可以将网格看作一个图，每个格子是一个节点，相邻且差值不超过 1 的格子之间有一条边。问题就转化为找到最大的连通分量。

解决这个问题的一个有效方法是使用深度优先搜索（DFS）或广度优先搜索（BFS）或者 并查集（DSU）。

这里以 DFS 为例来解释解题思路：

1. 遍历整个网格，对每个未访问的格子进行 DFS。
2. 在 DFS 过程中，检查当前格子的上下左右四个相邻格子。
3. 如果相邻格子未访问过，且与当前格子的差值绝对值不超过 1，则继续对该相邻格子进行 DFS。
4. 记录每次 DFS 访问的格子数量，取最大值作为结果。

实现时，可以使用一个二维数组来存储网格数据，另一个二维数组来标记已访问的格子。

DFS 函数可以返回当前连通区域的大小，主函数则负责遍历所有格子并更新最大连通区域的大小。

参考代码

• Python

import sys
sys.setrecursionlimit(1000000)  # 增加递归深度限制

def dfs(grid, visited, i, j, m, n):
    # 如果越界或已访问，返回0
    if i < 0 or i >= m or j < 0 or j >= n or visited[i][j]:
        return 0
    
    visited[i][j] = True
    count = 1
    
    # 四个方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for di, dj in directions:
        ni, nj = i + di, j + dj
        if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
            if abs(grid[ni][nj] - grid[i][j]) <= 1:
                count += dfs(grid, visited, ni, nj, m, n)
    
    return count

# 读取输入
m, n = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(m)]

# 初始化访问数组
visited = [[False] * n for _ in range(m)]

max_area = 0

# 遍历每个格子
for i in range(m):
    for j in range(n):
        if not visited[i][j]:
            max_area = max(max_area, dfs(grid, visited, i, j, m, n))

# 输出结果
print(max_area)

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 150

int grid[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int m, n;

int dfs(int i, int j) {
    // 如果越界或已访问,返回0
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) {
        return 0;
    }
    
    visited[i][j] = 1;  // 标记当前格子为已访问
    int count = 1;  // 当前格子计入连通区域
    
    // 四个方向:上、下、左、右
    int di[] = {-1, 1, 0, 0};
    int dj[] = {0, 0, -1, 1};
    
    for (int k = 0; k < 4; k++) {
        int ni = i + di[k];
        int nj = j + dj[k];
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
            if (abs(grid[ni][nj] - grid[i][j]) <= 1) {  // 检查相邻格子是否满足条件
                count += dfs(ni, nj);  // 递归访问相邻格子
            }
        }
    }
    
    return count;  // 返回连通区域的大小
}

int main() {
    scanf("%d %d", &m, &n);
    
    // 读取网格数据
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    
    memset(visited, 0, sizeof(visited));  // 初始化访问数组
    int max_area = 0;
    
    // 遍历每个格子
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                int area = dfs(i, j);
                if (area > max_area) {
                    max_area = area;