华为OD E卷(100分)22-机器人的活动区域

ops/2024/12/19 22:20:46/

前言

        工作了十几年,从普通的研发工程师一路成长为研发经理、研发总监。临近40岁,本想辞职后换一个相对稳定的工作环境一直干到老, 没想到离职后三个多月了还没找到工作,愁肠百结。为了让自己有点事情做,也算提高一下自己的编程能力,无聊之余打算用一些大厂的编程题练练手。希望通过这些分享能够帮到一些人,也希望能和看到此文的大神们沟通交流,提升自己,更希望在此期间能够找到一份理想的工作。

题目描述

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

示例 

示例1

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

输出
6

说明

1252
2445
3571
4624

图中红色区域,相邻网格差值绝对值都小于等于 1 ,且为最大区域,对应网格点数目为 6。

示例1

输入
2 3
1 3 5
4 1 3

输出
1

说明

任意两个相邻网格的差值绝对值都大于1,机器人不能在网格间移动,只能在单个网格内活动,对应网格点数目为1

解题思路

        定义上下左右方向,使用DFS搜索算法进行探索,取最大路径数。

题解

Java实现

package huawei.e100;import java.util.Arrays;
import java.util.Scanner;/**
* @author arnold
* @date 2024年12月14日*/
public class T22 {static final int[][] OFFSET = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {int m = sc.nextInt();int n = sc.nextInt();int[][] data = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {data[i][j] = sc.nextInt();}}int maxCanPlayEara = 0;// 对所有格子逐个探索,取步数最大值for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {boolean[][] dataUsed = new boolean[m][n];int canPlayCount = run(data, m, n, i, j, dataUsed);maxCanPlayEara = Math.max(maxCanPlayEara, canPlayCount);}}System.out.println(maxCanPlayEara);}}static int run(int[][] data, int m, int n, int startM, int startN, boolean[][] dataUsed) {int canPlayCount = 1; // 定义活动范围dataUsed[startM][startN] = true; // 标记当前点已经访问过// 遍历四个方向for(int[] d :OFFSET) {int dm = startM + d[0];int dn = startN + d[1];// 到达边界跳过。if (dm < 0 || dm >=m || dn <0 || dn >= n) {continue;}if (Math.abs(data[dm][dn] - data[startM][startN]) <=1 && dataUsed[dm][dn] == false) {canPlayCount += run(data, m, n, dm, dn, dataUsed);}}return canPlayCount;}
}

http://www.ppmy.cn/ops/143296.html

相关文章

【卷积神经网络】LeNet实践

模型建立 数据初始化根据模型搭建前向传播打印模型结构 前向传播数据初始化 def __init__(self):super(LeNet, self).__init__()# 第一层卷积层&#xff1a;# 输入&#xff1a;灰度图像 (1通道&#xff0c;大小 28x28)# 输出&#xff1a;6个特征图 (大小 28x28, 通过padding2保…

Flutter环境搭建

1.Flutter 简介 1.1 Flutter 是什么 &#xff1f; Flutter 是一个 UI SDK&#xff08;Software Development Kit&#xff09;跨平台解决方案&#xff1a;可以实现一套代码发布移动端&#xff08;iOS、Android、HarmonyOS&#xff09;、Web端、桌面端目前很多公司都在用它&…

红黑树与布隆过滤器的了解

红黑树介绍 红黑树&#xff08;Red Black Tree&#xff09;是一种自平衡二叉查找树。它是在 1972 年由 Rudolf Bayer 发明的&#xff0c;当时被称为平衡二叉 B 树&#xff08;symmetric binary B-trees&#xff09;。后来&#xff0c;在 1978 年被 Leo J. Guibas 和 Robert Sed…

Python 参数配置使用 XML 文件的教程 || Python打包 || 模型部署

当配置项存储在外部文件&#xff08;如 XML、JSON&#xff09;时&#xff0c;修改配置无需重新编译和发布代码。通过更新 XML 文件即可调整参数&#xff0c;无需更改源代码&#xff0c;从而提升开发效率和代码可维护性。 1. 为什么选择 XML 配置文件 XML 配置文件具有多种优点…

校园点餐订餐外卖跑腿Java源码

简介&#xff1a; 一个非常实用的校园外卖系统&#xff0c;基于 SpringBoot 和 Vue 的开发。这一系统源于黑马的外卖案例项目 经过站长的进一步改进和优化&#xff0c;提供了更丰富的功能和更高的可用性。 这个项目的架构设计非常有趣。虽然它采用了SpringBoot和Vue的组合&am…

Android上dump layer的方法

在 Android 上&#xff0c;dump layer 是一种调试工具&#xff0c;用来获取 SurfaceFlinger 的图形层数据&#xff08;Layer&#xff09;以排查显示问题。以下是常用的 dump Layer 方法&#xff1a; 1. 使用 dumpsys SurfaceFlinger dumpsys 是 Android 提供的强大的系统调试工…

AI开发 - 用GPT写一个GPT应用的真实案例

就在昨天&#xff0c;我的同事推荐给我了一个第三方的公共大模型API&#xff0c;这个API集合了国际上上几乎所有知名的大模型&#xff0c;只需要很少的费用&#xff0c;就可以接入到这些大模型中并使用它们。成本之低&#xff0c;令人乍舌&#xff01;包括我们现在无法试用的 G…

java client http请求 返回数据 实时循环监听 url 中资源是否生成

1、php 中 执行 exec 调用操作系统 命令行 执行 以下 java 代码 生成 的jar 2、php 执行命令是 以上1 需要命令行 输入 参数 taskid 3、实现实时监听 MP3 url 是否生成 4、 package com.example.filedemo.controller;import java.io.BufferedReader; import java.io.InputStre…