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

OD统一考试

题解： Java / Python / C++

alt

题目描述

现有一个机器人，可放置于 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

题解

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

解题思路：

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

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

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

Java

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 = scanner.nextInt();
        n = scanner.nextInt();

        g = new int[m][n];
        vis = new boolean[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                g[i][j] = scanner.nextInt();
            }
        }

        int maxRange = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                maxRange = Math.max(maxRange, dfs(i, j));
            }
        }

        System.out.println(maxRange);
    }
}

Python

python">from itertools import pairwise


m, n = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]
# 是否已经被访问计数
vis = [[False] * n for _ in range(m)]
dirs = [-1, 0, 1, 0, -1]


def dfs(r: int, c: int) -> int:
    """机器人在(r, c)可活动的最大范围对应的网格点数目(已经被标记访问就不参与计数，避免重复计数提高性能)"""
    if vis[r][c]:
        return 0

    vis[r][c] = True
    cnt = 1

    # 向（r,c）的四个方向拓展
    for dr, dc in pairwise(dirs):
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n and not vis[nr][nc] and abs(g[nr][nc] - g[r][c]) <= 1:
            cnt += dfs(nr, nc)
    return cnt


max_rage = max([dfs(r, c) for r in range(m) for c in range(n)])
print(max_rage)

C++

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_M = 150 + 5;
const int MAX_N = 150 + 5;

int m, n;
int g[MAX_M][MAX_N];
bool vis[MAX_M][MAX_N];
const int dirs[] = {-1, 0, 1, 0, -1};

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

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

    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] && abs(g[nr][nc] - g[r][c]) <= 1) {
            cnt += dfs(nr, nc);
        }
    }

    return cnt;
}

int main() {
    cin >> m >> n;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }

    int max_range = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            max_range = max(max_range, dfs(i, j));
        }
    }

    cout << max_range << endl;

    return 0;
}