【华为OD-E卷-机器人活动区域 100分（python、java、c++、js、c）】

javacjsc_0">【华为OD-E卷-机器人活动区域 100分（python、java、c++、js、c）】

题目

现有一个机器人，可放置于 M × N 的网格中任意位置，每个网格包含一个非负整数编号，当相邻网格的数字编号差值的绝对值小于等于 1 时，机器人可以在网格间移动。
问题：求机器人可活动的最大范围对应的网格点数目。
说明：
网格左上角坐标为 (0,0) ,右下角坐标为(m−1,n−1) 机器人只能在相邻网格间上下左右移动

输入描述

第 1 行输入为 M 和 N

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

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

输出描述

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

行首行尾无多余空格

用例

用例一：

输入：

输出：

用例二：

输入：

2 3
1 3 5
4 1 3

输出：

python解法

解题思路：
问题分析：

给定一个矩阵，每个元素代表一个数字，我们需要找出矩阵中最大区域的大小。该区域由相邻的元素组成，两个相邻的元素的差的绝对值必须小于等于 1。区域中的元素可以通过上下左右四个方向相邻。
思路：

广度优先搜索 (BFS)：我们可以从矩阵中的每个未访问的元素开始，使用 BFS 遍历所有与其差值小于等于 1 的相邻元素，找出一个连通区域，计算该区域的大小。
最大区域：遍历矩阵中每个未访问的元素，执行 BFS，更新最大区域的大小。
细节：

BFS 的实现：使用队列 queue 来进行 BFS，每次从队列中取出一个元素，检查其四个方向的相邻元素，如果满足条件（未访问且差值小于等于 1），将其加入队列。
visited 数组：用来标记矩阵中哪些元素已经被访问，避免重复遍历。
复杂度：假设矩阵的大小为 m * n，由于每个元素最多被访问一次，时间复杂度为 O(m * n)。

from collections import deque# 使用广度优先搜索 (BFS) 计算一个连通区域的大小
def bfs(matrix, visited, i, j, m, n):queue = deque([(i, j)])  # 初始化队列，开始节点是 (i, j)count = 0  # 当前区域的元素计数offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右四个方向的偏移量while queue:x, y = queue.popleft()  # 弹出队列中的元素 (x, y)if visited[x][y]:  # 如果该点已经访问过，跳过continuevisited[x][y] = True  # 标记该点为已访问count += 1  # 计数当前区域的元素数量# 遍历四个方向的相邻点for offsetX, offsetY in offsets:newX, newY = x + offsetX, y + offsetY  # 计算相邻点的坐标if 0 <= newX < m and 0 <= newY < n and not visited[newX][newY]:  # 确保新点在矩阵范围内并且未被访问if abs(matrix[x][y] - matrix[newX][newY]) <= 1:  # 如果当前点与新点的差值小于等于1queue.append((newX, newY))  # 将新点加入队列继续扩展return count  # 返回当前连通区域的大小# 查找矩阵中最大的连通区域
def find_largest_area(matrix, m, n):visited = [[False for _ in range(n)] for _ in range(m)]  # 初始化访问标记数组max_area = 0  # 存储最大区域的大小# 遍历整个矩阵for i in range(m):for j in range(n):if not visited[i][j]:  # 如果当前点没有被访问过# 执行 BFS，计算当前连通区域的大小max_area = max(max_area, bfs(matrix, visited, i, j, m, n))return max_area  # 返回最大区域的大小# 输入矩阵的尺寸 m 和 n
m, n = map(int, input().split())
# 输入矩阵内容
matrix = [list(map(int, input().split())) for _ in range(m)]# 输出最大连通区域的大小
print(find_largest_area(matrix, m, n))

java_125">java解法

解题思路
问题分析：
给定一个 m x n 的矩阵 grid，我们需要找出矩阵中最大的“区域”，区域中的元素满足以下条件：任意两个相邻元素的差值不大于 1，且区域内的元素必须是连通的（即它们通过上下左右方向相邻）。
思路：
我们可以使用广度优先搜索 (BFS) 来探索每个未访问的区域。BFS 会遍历与当前点差值不大于 1 的所有相邻点，并计算区域的大小。
最大区域：遍历整个矩阵，对于每一个未访问的点，执行一次 BFS，计算该区域的大小，并更新最大区域的大小。
细节：
使用一个 visited 数组记录哪些点已经访问过，避免重复计算。
通过一个队列实现 BFS，探索上下左右相邻点。
每次 BFS 执行时，如果当前点与相邻点的差值小于等于 1，则将该相邻点加入队列进行进一步遍历。
复杂度：假设矩阵的大小为 m x n，每个点最多被访问一次，BFS 的复杂度是 O(m * n)，因此总时间复杂度为 O(m * n)。

java">import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取矩阵的行数和列数int m = sc.nextInt();int n = sc.nextInt();// 读取矩阵内容int[][] grid = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}// 输出最大区域的大小System.out.println(getResult(grid, m, n));}// 计算矩阵中最大的连通区域的大小public static int getResult(int[][] grid, int m, int n) {boolean[][] visited = new boolean[m][n]; // 访问标记数组int maxSize = 0;  // 记录最大的区域大小// 四个方向的偏移量，上下左右int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 遍历整个矩阵for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 如果当前点没有被访问过，执行 BFS 计算该区域的大小if (!visited[i][j]) {int size = bfs(grid, visited, i, j, m, n, dirs);// 更新最大区域的大小maxSize = Math.max(maxSize, size);}}}return maxSize;  // 返回最大的区域大小}// 使用 BFS 查找从 (x, y) 出发的连通区域的大小private static int bfs(int[][] grid, boolean[][] visited, int x, int y, int m, int n, int[][] dirs) {Queue<int[]> queue = new LinkedList<>();  // BFS 使用的队列queue.offer(new int[]{x, y});  // 将起始点加入队列visited[x][y] = true;  // 标记起始点为已访问int size = 1;  // 当前区域的大小，从起始点开始// 当队列不为空时，继续遍历while (!queue.isEmpty()) {int[] point = queue.poll();  // 弹出队列中的一个元素// 遍历当前点的四个方向for (int[] dir : dirs) {int newX = point[0] + dir[0];  // 计算新点的横坐标int newY = point[1] + dir[1];  // 计算新点的纵坐标// 确保新点在矩阵范围内，并且未被访问过// 同时新点与当前点的差值小于等于 1，才将新点加入队列if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]&& Math.abs(grid[point[0]][point[1]] - grid[newX][newY]) <= 1) {visited[newX][newY] = true;  // 标记新点为已访问queue.offer(new int[]{newX, newY});  // 将新点加入队列size++;  // 增加当前区域的大小}}}return size;  // 返回当前区域的大小}
}

C++解法

解题思路

更新中

C解法

解题思路
问题分析：

给定一个 m x n 的矩阵 values，其中每个元素代表一个数字。我们需要计算矩阵中所有符合条件的连通区域的大小，区域中的元素需要满足以下条件：
任意两个相邻元素的差值不大于 1。
相邻元素通过上下左右方向相连。
思路：

我们可以使用深度优先搜索 (DFS) 来遍历每个连通区域。DFS 从一个未访问的点开始，探索所有符合条件的相邻点，直到无法再扩展为止。每次 DFS 执行完后，我们可以得到一个连通区域的大小。
最大区域：遍历整个矩阵，找到最大的连通区域，更新最大区域的大小。
细节：

使用一个 traversed 数组来标记哪些元素已经访问过，避免重复计算。
每次 DFS 调用时，如果当前点与相邻点的差值小于等于 1，则递归访问相邻点。
通过四个方向的偏移量 (shifts) 来控制上下左右方向的探索。
复杂度：假设矩阵的大小为 rows x cols，每个点最多被访问一次，因此时间复杂度是 O(rows * cols)，即 O(n)，其中 n 是矩阵中的元素个数。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>#define MAX_DIM 150  // 定义矩阵的最大尺寸int rows, cols;  // 矩阵的行数和列数
int values[MAX_DIM][MAX_DIM];  // 存储矩阵的值
bool traversed[MAX_DIM][MAX_DIM] = {false};  // 访问标记数组，初始状态下所有元素都没有被访问
int shifts[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // 上下左右四个方向的偏移量// 深度优先搜索 (DFS) 函数，用来计算从 (r, c) 出发的连通区域的大小
int depth_search(int r, int c, int steps) {for (int d = 0; d < 4; d++) {  // 遍历四个方向int next_r = r + shifts[d][0];  // 计算下一个行坐标int next_c = c + shifts[d][1];  // 计算下一个列坐标// 判断新点是否在矩阵范围内，且与当前点的差值小于等于 1，并且没有被访问过if (next_r >= 0 && next_r < rows && next_c >= 0 && next_c < cols &&abs(values[next_r][next_c] - values[r][c]) <= 1 && !traversed[next_r][next_c]) {traversed[next_r][next_c] = true;  // 标记新点为已访问steps = depth_search(next_r, next_c, steps + 1);  // 递归访问新点，增加区域大小}}return steps;  // 返回当前连通区域的大小
}int main() {// 输入矩阵的尺寸scanf("%d %d", &rows, &cols);// 输入矩阵的元素for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {scanf("%d", &values[r][c]);}}int max_region = 0;  // 记录最大区域的大小// 遍历整个矩阵，寻找未访问的点，并执行 DFS 计算连通区域的大小for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {// 如果当前点没有被访问过，执行 DFS 查找连通区域if (!traversed[r][c]) {traversed[r][c] = true;  // 标记当前点为已访问int region = depth_search(r, c, 1);  // 从当前点开始 DFS，区域初始大小为 1if (region > max_region) max_region = region;  // 更新最大区域大小}}}// 输出最大区域的大小printf("%d\n", max_region);return 0;
}

JS解法

解题思路

javascript">更新中

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏