题目描述

给定一个大小为 $M \times N$ 的网格，每个网格包含一个非负整数编号（$0 \leq k \leq 50$）。机器人可以从任意位置开始，且只能在相邻网格（上下左右）间移动。当相邻网格的数字编号差值的绝对值小于等于 $1$ 时，机器人可以在网格间移动。

求机器人可活动的最大范围对应的网格点数目，即满足移动条件的最大连通区域的大小。

思路

这是一个典型的网格中的连通区域问题。我们需要找到满足特定条件的最大连通区域的大小。

具体步骤：

1. 遍历网格： 对于每一个未被访问过的网格点，进行搜索。

2. 深度优先搜索（DFS）或广度优先搜索（BFS）： 从当前网格点出发，搜索所有满足条件的相邻网格。

   • 移动条件： 当前网格点与相邻网格点的数字编号差值的绝对值小于等于 $1$。

3. 记录区域大小： 在搜索过程中，统计连通区域的大小。

4. 更新最大值： 比较并更新最大连通区域的大小。

5. 重复步骤1-4： 直到所有的网格点都被访问过。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int dx[4] = {0, 0, -1, 1}; // 上下左右移动
const int dy[4] = {-1, 1, 0, 0};

int M, N;
vector<vector<int>> grid;
vector<vector<bool>> visited;

int dfs(int x, int y) {
    visited[x][y] = true;
    int count = 1; // 当前网格点计数为1

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 检查边界
        if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
            // 检查是否已访问以及数字差值条件
            if (!visited[nx][ny] && abs(grid[x][y] - grid[nx][ny]) <= 1) {
                count += dfs(nx, ny);
            }
        }
    }
    return count;
}

int main() {
    cin >> M >> N;
    grid.resize(M, vector<int>(N));
    visited.resize(M, vector<bool>(N, false));

    for (int i = 0; i < M; ++i)
        for (int j = 0; j < N; ++j)
            cin >> grid[i][j];

    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);
                max_area = max(max_area, area);
            }

    cout << max_area << endl;
    return 0;
}

python

M, N = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(M)]
visited = [[False]*N for _ in range(M)]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y):
    visited[x][y] = True
    count = 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < M and 0 <= ny < N:
            if not visited[nx][ny] and abs(grid[x][y] - grid[nx][ny]) <= 1:
                count += dfs(nx, ny)
    return count

max_area = 0

for i in range(M):
    for j in range(N):
        if not visited[i][j]:
            area = dfs(i, j)
            max_area = max(max_area, area)

print(max_area)

java

import java.util.Scanner;

public class Main {
    static int M, N;
    static int[][] grid;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1}; // 上下左右
    static int[] dy = {-1, 1, 0, 0};

    static int dfs(int x, int y) {
        visited[x][y] = true;
        int count = 1;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
                if (!visited[nx][ny] && Math.abs(grid[x][y] - grid[nx][ny]) <= 1) {
                    count += dfs(nx, ny);
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        grid = new int[M][N];
        visited = new boolean[M][N];

        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
                grid[i][j] = sc.nextInt();

        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);
                    max_area = Math.max(max_area, area);
                }

        System.out.println(max_area);
    }
}

题目内容

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

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

说明：

1. 网格左上角坐标为 $(0,0)$ ,右下角坐标为 $(m−1,n−1)$
2. 机器人只能在相邻网格间上下左右移动

示例1 输入如下网格

输出：$6$

说明：图中绿色区域，相邻网格差值绝对值都小于等于 $1$ ，且为最大区域，对应网格点数目为 $6$

示例2 输入如下网格

输出：$1$

说明：任意两个相邻网格的差值绝对值都大于 $1$，机器人不能在网格间移动，只能在单个网格内活动，对应网格点数目为 $1$

输入描述

第 $1$ 行输入为 $M$ 和 $N$

• $M$ 表示网格的行数
• $N$ 表示网格的列数

之后 $M$ 行表示网格数值，每行 $N$ 个数值（数值大小用 $k$ 表示），数值间用单个空格分隔，行首行尾无多余空格。

• $M、 N、 k$ 均为整数
• $1 ≤ M,N ≤ 150$
• $0 ≤ k ≤ 50$

输出描述

输出 $1$ 行，包含 $1$ 个数字，表示最大活动区域的网格点数目，

行首行尾无多余空格。

样例1

输入

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

输出

6

说明

见题目内容中示例 $1$，最大区域对应网格点数目为 $6$

样例2

输入

2 3
1 3 5
4 1 3

输出

1

说明

见题目内容中示例 $2$，最大区域对应网格点数目为 $1$