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

25-03-07 19:03

3448

5528

blog.csdn.net

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为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
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2
3
4
5

输出：

6
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例二：

输入：

2 3
1 3 5
4 1 3
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2
3

输出：

1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

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))

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

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;  // 返回当前区域的大小
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

C解法

解题思路
问题分析：

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

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

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

#include 
#include 
#include 

#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，区域初始大小为 1
                if (region > max_region) max_region = region;  // 更新最大区域大小
            }
        }
    }

    // 输出最大区域的大小
    printf("%d\n", max_region);
    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">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解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

注意：

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

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144533289"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

注册

评论记录：

未查询到任何数据！