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

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

题目描述

现有一个机器人，可放置于 M x N 的网格中任意位置，每个网格包含一个非负整数编号，当相邻网格的数字编号差值的绝对值小于等于 1 时机器人可以在网格间移动。

问题: 求机器人可活动的最大范围对应的网格点数目。

输入描述

第 1 行入为 M 和N， M 表示网格的行数 N表示网格的列数

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

输出描述

输出 1行，包含 1个数字，表示最大活动区域的网格点数目, 行首行尾无多余空格。

示例1

题解

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

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;
}

什码情况