【华为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 个数字，表示最大活动区域的网格点数目，
行首行尾无多余空格
用例
用例一：
输入：
4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4
- 1
- 2
- 3
- 4
- 5
输出：
6
- 1
用例二：
输入：
2 3
1 3 5
4 1 3
- 1
- 2
- 3
输出：
1
- 1
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]: # 如果该点已经访问过，跳过
continue
visited[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: # 如果当前点与新点的差值小于等于1
queue.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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
java解法
- 解题思路
- 问题分析：
给定一个 m x n 的矩阵 grid，我们需要找出矩阵中最大的“区域”，区域中的元素满足以下条件：任意两个相邻元素的差值不大于 1，且区域内的元素必须是连通的（即它们通过上下左右方向相邻）。
思路：
我们可以使用 广度优先搜索 (BFS) 来探索每个未访问的区域。BFS 会遍历与当前点差值不大于 1 的所有相邻点，并计算区域的大小。
最大区域：遍历整个矩阵，对于每一个未访问的点，执行一次 BFS，计算该区域的大小，并更新最大区域的大小。
细节：
使用一个 visited 数组记录哪些点已经访问过，避免重复计算。
通过一个队列实现 BFS，探索上下左右相邻点。
每次 BFS 执行时，如果当前点与相邻点的差值小于等于 1，则将该相邻点加入队列进行进一步遍历。
复杂度：假设矩阵的大小为 m x n，每个点最多被访问一次，BFS 的复杂度是 O(m * n)，因此总时间复杂度为 O(m * n)。
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; // 返回当前区域的大小
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
C++解法
- 解题思路
更新中
- 1
C解法
给定一个 m x n 的矩阵 values，其中每个元素代表一个数字。我们需要计算矩阵中所有符合条件的连通区域的大小，区域中的元素需要满足以下条件：
任意两个相邻元素的差值不大于 1。
相邻元素通过上下左右方向相连。
思路：
我们可以使用 深度优先搜索 (DFS) 来遍历每个连通区域。DFS 从一个未访问的点开始，探索所有符合条件的相邻点，直到无法再扩展为止。每次 DFS 执行完后，我们可以得到一个连通区域的大小。
最大区域：遍历整个矩阵，找到最大的连通区域，更新最大区域的大小。
细节：
使用一个 traversed 数组来标记哪些元素已经访问过，避免重复计算。
每次 DFS 调用时，如果当前点与相邻点的差值小于等于 1，则递归访问相邻点。
通过四个方向的偏移量 (shifts) 来控制上下左右方向的探索。
复杂度：假设矩阵的大小为 rows x cols，每个点最多被访问一次，因此时间复杂度是 O(rows * cols)，即 O(n)，其中 n 是矩阵中的元素个数。
#include - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
JS解法
更新中
- 1
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：