`
betakoli
  • 浏览: 168454 次
社区版块
存档分类
最新评论

华为上机题之Word Maze(单词迷宫)

 
阅读更多

Word Maze 是一个网络小游戏,你需要找到以字母标注的食物,但要求以给定单词字母的顺序吃掉。如上图,假设给定单词if,你必须先吃掉i然后才能吃掉f。


    但现在你的任务可没有这么简单,你现在处于一个迷宫Maze(n×m的矩阵)当中,里面到处都是以字母标注的食物,但你只能吃掉能连成给定单词W的食物。


如下图,指定W为“SOLO”,则在地图中红色标注了单词“SOLO”。 

 

注意区分英文字母大小写,你只能上下左右行走。

输入:

5 5

SOLO

CPUCY

EKLQH

CRSOL

EKLQO

PGRBC

输出:

YES

 

这道题目比较基础,遍历数组找到开头字母,再BFS或者DFS遍历就可以找到了。但是需要注意一点,就是字母不能重用,比如上面输入“SOLO”输出YES,但输入“SOLOL”则没返回结果,因为'L'重用。

 

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	static boolean result = false;

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n = 0, m = 0;
		if (cin.hasNext()) {
			n = cin.nextInt();
			m = cin.nextInt();
		}
		String target = cin.next();
		char arrs[][] = new char[n][m];
		int i = 0;
		while (cin.hasNext()) {
			String temp = cin.next();
			for (int j = 0; j < temp.length(); j++) {
				arrs[i][j] = temp.charAt(j);
			}
			i++;
			if (i == n)
				break;
		}

		char first = target.charAt(0);
		for (i = 0; i < arrs.length; i++) {
			for (int j = 0; j < arrs[i].length; j++) {
				if (arrs[i][j] == first) {
					HashSet set = new HashSet();
					find(arrs, n, m, i, j, target, set);
					if (result)
						break;
				}
			}
		}
	}

	private static void find(char[][] arrs, int n, int m, int i, int j,
			String target, HashSet hashSet) {
		// TODO Auto-generated method stub
		char first = target.charAt(0);
		if (arrs[i][j] != first) {
			return;
		}
		if (hashSet.contains(i + j)) {
			return;
		}
		if (target.length() == 1) {
			System.out.println("YES");
			result = true;
			return;
		}
		hashSet.add(i + j);
		target = target.substring(1);
		for (int len = 0; len < 4; len++) {
			HashSet temp = new HashSet(hashSet);
			switch (len) {
			case 0:
				if (i > 0)
					find(arrs, n, m, i - 1, j, target, temp);
				else
					return;
				break;
			case 1:
				if (i < n - 1)
					find(arrs, n, m, i + 1, j, target, temp);
				else
					return;
				break;
			case 2:
				if (j > 0)
					find(arrs, n, m, i, j - 1, target, temp);
				else
					return;
				break;
			case 3:
				if (j < m - 1)
					find(arrs, n, m, i, j + 1, target, temp);
				else
					return;
				break;
			default:
				break;
			}
		}
	}
}

 

 

分享到:
评论

相关推荐

    华为2013.9.22上机试题

    通常,Word Maze问题可能会涉及到构造或解决基于字符的迷宫游戏,可能需要对字符或字符串进行位操作以生成或解码迷宫路径。 这些是根据给定的代码片段所涵盖的主要编程知识点。理解和掌握这些概念对于解决类似的...

    华为OD机试C卷- 迷宫问题(Java & JS & Python).md-私信看全套OD代码及解析

    本题目是华为OD机试中的经典算法题之一,主要考察考生对于图遍历算法的理解与实现能力,特别是对于广度优先搜索(BFS)的应用。 #### 题目描述 给定一个二维数组`N * M`,数组中的值为0或1,0代表可以通过的路径,...

    华为2014校园招聘长沙机试

    4. 数组和矩阵操作:第三题“Word Maze”可能要求解决迷宫问题,涉及到二维数组(矩阵)的处理,包括查找路径、判断可行路径等。数组和矩阵是数据结构的基础,对于解决许多实际问题,如图像处理、游戏设计等,都有...

    matlab-迷宫路径

    matlab代码,有标注,题目源自牛客网华为机试。 定义一个二维数组N*M(其中2;2),如5 × 5数组下所示: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它...

    【大厂面试专栏】一份Java程序员需要的技术指南,这里有面试题、系统架构

    【大厂面试专栏】一份Java程序员需要的技术指南,这里有面试题、系统架构、职场锦囊、主流中间件等,让你成为更牛的自己!_technology-talk

    flashocc-QAT-PTQ.zip

    flashocc-QAT-PTQ.zip

    大连理工大学城市学院在四川2020-2024各专业最低录取分数及位次表.pdf

    那些年,与你同分同位次的同学都去了哪里?全国各大学在四川2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据

    川北医学院在四川2020-2024各专业最低录取分数及位次表.pdf

    那些年,与你同分同位次的同学都去了哪里?全国各大学在四川2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据

    黑河学院在四川2020-2024各专业最低录取分数及位次表.pdf

    那些年,与你同分同位次的同学都去了哪里?全国各大学在四川2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据

    西安邮电大学在四川2020-2024各专业最低录取分数及位次表.pdf

    那些年,与你同分同位次的同学都去了哪里?全国各大学在四川2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据

    【光学】基于matlab两列单色平面波+合成【含Matlab源码 9007期】.zip

    CSDN海神之光上传的全部代码均可运行,亲测可用,尽我所能,为你服务; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,可私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、物理应用 仿真:导航、地震、电磁、电路、电能、机械、工业控制、水位控制、直流电机、平面电磁波、管道瞬变流、刚度计算 光学:光栅、杨氏双缝、单缝、多缝、圆孔、矩孔衍射、夫琅禾费、干涉、拉盖尔高斯、光束、光波、涡旋 定位问题:chan、taylor、RSSI、music、卡尔曼滤波UWB 气动学:弹道、气体扩散、龙格库弹道 运动学:倒立摆、泊车 天体学:卫星轨道、姿态 船舶:控制、运动 电磁学:电场分布、电偶极子、永磁同步、变压器

    文件比较工具、文件夹比较工具、linux、ubuntu、linx麒麟等免费使用多日

    文件比较工具、文件夹比较工具、linux、ubuntu、linx麒麟等免费使用多日

    Spire.XLS是一个基于.NET的组件,使用它我们可以创建Excel文件

    Spire.XLS是一个基于.NET的组件,使用它我们可以创建Excel文件,编辑已有的Excel并且可以转换Excel文件.zip

    【Unity完整游戏模板】Downhill Ride 轻松开发极限运动或竞速类的下坡滑行游戏

    文件名:Downhill Ride - Game Template 2020 LTS v1.2.3.unitypackage Downhill Ride - Game Template (2020 LTS) 是一个为 Unity 2020 LTS 版本开发的完整游戏模板,主要适用于开发极限运动或竞速类的下坡滑行游戏。这个模板专为快速原型设计和项目开发而打造,提供了关键功能和资源,帮助开发者轻松实现类似下坡竞速的游戏项目。 主要特点: 完整的游戏框架: 该模板包含基础的游戏逻辑,允许玩家通过控制角色在下坡道上滑行或骑行,避开障碍物并尽可能快速完成赛道。 物理与控制系统: 内置的物理引擎和角色控制器已经经过优化,可以实现平滑的下坡滑行体验,提供真实感十足的物理效果。 多种关卡支持: 模板支持多个关卡设计,开发者可以根据需要扩展或自定义不同难度的关卡。 UI 和交互设计: 包含基本的用户界面(UI)设计,带有主菜单、关卡选择、计分系统等功能,用户可以轻松扩展或定制这些 UI 元素。 优化的性能: 模板专为移动平台和桌面平台优化,确保良好的性能表现......

    Java课程设计之销售管理系统

    (1)课程设计项目简单描述 鉴于当今超市产品种类繁多,光靠人手动的登记已经不能满足一般商家的需求。我们编辑该程序帮助商家完成产品、商家信息的管理,包括产品、客户、供应商等相关信息的添加、修改、删除等功能。 (2)需求分析(或是任务分析) 1)产品类别信息管理:对客户的基本信息进行添加、修改和删除。 2)产品信息管理:对产品的基本信息进行添加、修改和删除。 3)供应商信息管理: 对供应商的基本信息进行添加、修改和删除。 4)订单信息管理:对订单的基本信 息进行添加、修改和删除。 5)统计报表:按选择日期期间,并按产品类别分组统 计订单金额,使用表格显示统计结果

    常州大学在四川2020-2024各专业最低录取分数及位次表.pdf

    那些年,与你同分同位次的同学都去了哪里?全国各大学在四川2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据

    yolo算法-工地佩戴头盔数据集-1608张图像带标签-epi-d4clr.zip

    yolo系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值

    Android System Webview(com.google.android.webvie) 125.0.6422.82

    Android System Webview(com.google.android.webvie) 125.0.6422.82 一般情况下设备可以从google play上更新,但是google play 中没有历史版本下载,所以在自己需要之后把资源上传

    VLP超低轮廓铜箔,全球前10强生产商排名及市场份额(by QYResearch).docx

    VLP超低轮廓铜箔,全球前10强生产商排名及市场份额(by QYResearch).docx

    南宁学院在四川2020-2024各专业最低录取分数及位次表.pdf

    那些年,与你同分同位次的同学都去了哪里?全国各大学在四川2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据

Global site tag (gtag.js) - Google Analytics