欢乐的周末 - 华为OD统一考试

2024-01-10 14:12

本文主要是介绍欢乐的周末 - 华为OD统一考试,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

OD统一考试

题解: Java / Python / C++

alt

题目描述

小华和小为是很要好的朋友,他们约定周末一起吃饭。

通过手机交流,他们在地图上选择了多个聚餐地点(由于自然地形等原因,部分聚餐地点不可达)。求小华和小为都能到达的聚餐地点有多少个?

输入描述

第一行输入m和n,m代表地图的长度,n代表地图的宽度

第二行开始具体输入地图信息,地图信息包含:

0 为通畅的道路

1 为障碍物 (且仅1为障碍物)

2 为小华或者小为,地图中必定有且仅有2个(非障碍物)

3 为被选中的聚餐地点 (非障碍物)

输出描述

可以被两方都到达的聚餐地点数量,行末无空格

示例1

输入:
4 4
2 1 0 3
0 1 2 1
0 3 0 0
0 0 0 0输出:
2说明:第一行输入地图的长宽为4,4,接下来4行是地图2表示华为的位置,3是聚餐地点,图中的两个3,小华和小为都可到达,所以输出2

示例2

输入
4 4
2 1 2 3
0 1 0 0
0 1 0 0
0 1 0 0输出
0

题解

这是一个 **DFS(深度优先搜索)**来解决的问题,主要目标是找到两个人(小华和小为)分别从他们的起点出发,能够到达的聚餐地点的交集。

主要思路是从两个起点分别进行深度优先搜索,并用一个二维数组 vis 记录访问状态。

在 DFS 过程中,将访问的位置的对应位设置为1,表示这个位置被访问过。

最后,遍历所有聚餐地点,如果两个人都能到达的地点,就将结果加一。

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/*** @author code5bug*/
public class Main {private static int m, n;private static void dfs(int[][] g, int r, int c, int[][] vis, int seq) {if (r < 0 || c < 0 || r >= m || c >= n || g[r][c] == 1 || ((vis[r][c] & (1 << seq)) != 0)) {return;}// 第 seq 个人访问(i,j) 则将 vis[i][j] 的二进制第 seq 位变为 1vis[r][c] |= (1 << seq);dfs(g, r + 1, c, vis, seq);dfs(g, r - 1, c, vis, seq);dfs(g, r, c + 1, vis, seq);dfs(g, r, c - 1, vis, seq);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);m = scanner.nextInt();n = scanner.nextInt();int[][] g = new int[m][n];int[][] vis = new int[m][n];// 起点位置(小华或者小为的位置)List<int[]> starts = new ArrayList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {g[i][j] = scanner.nextInt();if (g[i][j] == 2) starts.add(new int[]{i, j});}}for (int i = 0; i < 2; i++) {int[] pos = starts.get(i);dfs(g, pos[0], pos[1], vis, i);}int result = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 聚餐地点 && 两次都访问到if (g[i][j] == 3 && vis[i][j] == 3) {result++;}}}System.out.println(result);}
}

Python

def dfs(g, r, c, vis, seq):if r < 0 or c < 0 or r >= m or c >= n or g[r][c] == 1 or (vis[r][c] & (1 << seq)) != 0:return# 第 seq 个人访问(i,j) 则将 vis[i][j] 的二进制第 seq 位变为 1vis[r][c] |= (1 << seq)dfs(g, r + 1, c, vis, seq)dfs(g, r - 1, c, vis, seq)dfs(g, r, c + 1, vis, seq)dfs(g, r, c - 1, vis, seq)m, n = map(int, input().split())g = [list(map(int, input().split())) for _ in range(m)]
vis = [[0] * n for _ in range(m)]# 起点位置(小华或者小为的位置)
starts = [(r, c) for r in range(m) for c in range(n) if g[r][c] == 2]
for seq, (r, c) in enumerate(starts):dfs(g, r, c, vis, seq)result = sum(1 for r in range(m) for c in range(n) if g[r][c] == 3 and vis[r][c] == 3)
print(result)

C++

#include <iostream>
#include <vector>
#include <utility>using namespace std;int m, n;void dfs(vector<vector<int>>& g, int r, int c, vector<vector<int>>& vis, int seq) {if(r < 0 || c < 0 || r >= m || c >= n || g[r][c] == 1 || (vis[r][c] & (1 << seq))) return;vis[r][c] |= (1 << seq);dfs(g, r + 1, c, vis, seq);dfs(g, r - c, c, vis, seq);dfs(g, r, c + 1, vis, seq);dfs(g, r, c - 1, vis, seq);
}int main() {cin >> m >> n;vector<pair<int, int>> starts; // 起点位置(小华或者小为的位置)vector<vector<int>> g(m, vector<int>(n, 0));for(int i=0; i<m; i++) {for(int j=0; j<n; j++) {cin >> g[i][j];if(g[i][j] == 2) {starts.push_back({i, j});}}}// vis[i][j] 表示访问状态, 第 seq 个人访问(i,j) 则将 vis[i][j] 的二进制第 seq 位变为 1vector<vector<int>> vis(m, vector<int>(n, 0));for(int i=0; i < 2; i++) {dfs(g, starts[i].first, starts[i].second, vis, i);}int result = 0;for(int i=0; i<m; i++) {for(int j= 0; j<n; j++) {// 聚餐地点 && 两次都访问到if(g[i][j] == 3 && vis[i][j] == 3) {result ++;}}}cout << result << endl;return 0;
}

🙏整理题解不易, 如果有帮助到您,请给点个赞 ‍❤️‍ 和收藏 ⭐,让更多的人看到。🙏🙏🙏

这篇关于欢乐的周末 - 华为OD统一考试的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/591078

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群 华为云最近正在举办828 B2B企业节,Flexus X实例的促销力度非常大,特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Nginx等服务的需求,一定不要错过这个机会。赶紧去看看吧! 什么是华为云Flexus X实例 华为云Flexus X实例云服务是新一代开箱即用、体

没睡够,周末补觉好不好

中国睡眠研究会调查显示,中国成年人失眠的发生率高达38.2%。此外,40%的成年人在最近一个月内出现白天打盹。中国睡眠研究会还发现,1900年以来,人们的日睡眠时间以每年0.71分钟的速度递减。即我们当前的日睡眠时间比1900年减少了1.5小时。睡不够,怎么办? 周末补觉有助健康 失眠症对生活质量的负面影响很大。失眠者中的抑郁症发病率比非失眠者高3到4倍。但调查结果显示,我国失眠患

华为OD机试真题-学生方阵-2024年OD统一考试(E卷)

题目描述 学校组织活动,将学生排成一个矩形方阵。 请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上,方向可以是水平的,垂直的,成对角线的或者呈反对角线的。 注:学生个数不会超过10000 输入描述 输入的第一行为矩阵的行数和列数, 接下来的 n行为矩阵元素,元素间用""分隔。 输出描述 输出一个整数,表示矩阵中最长的位

UML- 统一建模语言(Unified Modeling Language)创建项目的序列图及类图

陈科肇 ============= 1.主要模型 在UML系统开发中有三个主要的模型: 功能模型:从用户的角度展示系统的功能,包括用例图。 对象模型:采用对象、属性、操作、关联等概念展示系统的结构和基础,包括类图、对象图、包图。 动态模型:展现系统的内部行为。 包括序列图、活动图、状态图。 因为要创建个人空间项目并不是一个很大的项目,我这里只须关注两种图的创建就可以了,而在开始创建UML图

华为 HCIP-Datacom H12-821 题库 (13)

有需要题库的可以看主页置顶 1.可以携带外部路由的 tag 标签信息的是以下哪一类 LSA? A、4 类 LSA B、5 类 LSA  C、3 类 LSA  D、2 类 LSA 答案:B 解析: 暂无解析 2..两台路由器直连,并设定网络类型为 p2p 建立OSPF 邻居。那么两台路由器传输 OSPF 报文的目的 IP 地址是以下哪一项? A、使用组播地址 224.0.0.6 B

4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器(MQTT协议)

MQTT协议概述 MQTT(Message Queuing Telemetry Transport)是一种轻量级的消息传输协议,它被设计用来提供一对多的消息分发和应用之间的通讯,尤其适用于远程位置的设备和高延迟或低带宽的网络。MQTT协议基于客户端-服务器架构,客户端可以订阅任意数量的主题,并可以发布消息到这些主题。服务器(通常称为MQTT Broker)则负责接受来自客户端的连接请求,并转发消