机器人活动区域 - 华为OD统一考试

OD统一考试

题解： Java / Python / C++

题目描述

现有一个机器人，可放置于 M x 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个数字，表示最大活动区域的网格点数目, 行首行尾无多余空格。

示例1

输入：
4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4

输出
6

题解

这是一个深度优先搜索（DFS）的问题，通过遍历网格中的每个点，使用DFS计算以该点为起点的可活动最大范围。在DFS过程中，通过标记访问数组 vis 来避免重复计数。

解题思路：

1. 从网格的每一个点出发，进行DFS，计算以该点为起点的可活动最大范围。
2. 使用DFS时，遍历当前点的四个方向，如果相邻网格的数字编号差值的绝对值小于等于1，并且相邻网格没有被访问过，则可以继续DFS。
3. 使用一个二维数组 vis 来标记已经访问的网格，防止重复计数。
4. 遍历所有点，找到最大的可活动范围。

时间复杂度：O(M * N)，其中 M 为网格的行数，N 为网格的列数。

空间复杂度：O(M * N)，需要额外的二维数组 vis 来标记访问状态。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    static int m, n;
    static int[][] g;
    static boolean[][] vis;
    static int[] dirs = {-1, 0, 1, 0, -1};

    public static int dfs(int r, int c) {
        if (vis[r][c]) {
            return 0;
        }

        vis[r][c] = true;
        int cnt = 1;

        // 向（r,c）的四个方向拓展
        for (int i = 0; i < 4; ++i) {
            int nr = r + dirs[i];
            int nc = c + dirs[i + 1];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc] && Math.abs(g[nr][nc] - g[r][c]) <= 1) {
                cnt += dfs(nr, nc);
            }
        }

        return cnt;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = s