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

华为上机题之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, }; 它...

    数学建模拟合与插值.ppt

    数学建模拟合与插值.ppt

    [net毕业设计]ASP.NET教育报表管理系统-权限管理模块(源代码+论文).zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、python、web、C#、EDA、proteus、RTOS等项目的源码。【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    mysql相关资源.txt

    mysql相关资源.txt

    利用HTML+CSS+JS的国漫分享网站(响应式)

    此项目为一个HTML+CSS+JS的国漫分享网站,用户可以在此网站中观看自己喜欢的国漫。此网站共有4个页面,分别为首页,最新动态,热门推荐,分类。页面动漫图片齐全,内容可更改。可用于期末课程设计或个人课程设计。

    Python爬虫爬取漫画

    Python爬虫爬取漫画

    C++语言编程用模拟退火算法解决旅行商问题

    模拟退火算法应用。C++语言编程用模拟退火算法解决旅行商问题。该资源包含模拟退火算法C++语言的源代码。模拟退火算法是一种基于概率的全局优化算法,最初来自于物理学中的退火过程。它通过模拟金属冷却时原子排列逐渐趋于最低能量状态的过程来寻找问题的最优解。模拟退火算法常用于解决非线性、组合优化问题,特别适合于大规模、复杂的搜索空间。

    传感器试题及答案.doc

    传感器试题及答案.doc

    [net毕业设计]ASP.NET网上书店(源代码+论文).zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、python、web、C#、EDA、proteus、RTOS等项目的源码。【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    MongoDB数据表基本操作中文最新版本

    本文档主要讲述的是MongoDB数据表基本操作;希望对大家会有帮助;感兴趣的朋友可以过来看看

    1-全国各省废气、废水排放二氧化硫、氮氧化物、烟尘、颗粒物排放量统计数据2011-2021年-社科数据.zip

    本数据集提供了2011至2021年间全国各省废气和废水中主要污染物的排放量统计数据。数据涵盖了二氧化硫、氮氧化物、烟尘和颗粒物等关键污染物的排放量,为研究中国环境状况和污染物排放趋势提供了宝贵信息。数据显示,2011-2021年间,各省的二氧化硫排放量从数十万吨到数百万吨不等,其中广东、广西、海南等省份的排放量较高。氮氧化物排放量同样显示出地域差异,北京、天津等北方城市的排放量相对较低,而一些工业大省如河北、山西的排放量较高。颗粒物排放量统计显示,工业源和生活源是主要的排放源,其中工业源排放量占比较大。这些数据不仅对环保政策制定者具有参考价值,也为学术研究提供了实证基础。

    脉冲宽度测量单片机课程设计.doc

    脉冲宽度测量单片机课程设计.doc

    [net毕业设计]ASP.NET在线毕业论文提交系统的设计与实现(源代码+论文).zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、python、web、C#、EDA、proteus、RTOS等项目的源码。【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    求职与招聘(源代码+论文+说明文档).zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、python、web、C#、EDA、proteus、RTOS等项目的源码。【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    [net毕业设计]ASP.NET视频点播系统的设计与实现(源代码+论文).zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、python、web、C#、EDA、proteus、RTOS等项目的源码。【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    全国矢量地图数据【国道+高速】-ArcGis Shape 格式数据集

    全国矢量地图数据【国道+高速公路】ArcGIS Shape格式数据集是一种专门用于地理信息系统(GIS)的矢量数据集,包含中国范围内国道和高速公路的详细路网信息。该数据集广泛应用于交通规划、导航、物流分析和灾害应急等领域,具有高精度和易用性。 数据集特点: 1. 数据内容: 国道:包括以“G”开头的国家级公路,如G1京哈高速、G107国道等。 高速公路:包括全国范围内的所有高速公路网,覆盖主要经济区、城市和边境口岸。 属性数据: 道路编号(国道或高速公路编号)。 道路名称。 道路等级(如一级、二级、快速路等)。 起点和终点坐标。 道路长度(单位:公里)。 相关属性(如路段建成年份、设计速度、车道数等)。 2. 数据格式: **Shapefile(.shp)**格式,支持主流GIS软件(如ArcGIS、QGIS)及数据处理工具(如Python、Matlab)。 3. 投影坐标系: 一般采用WGS84地理坐标系,或可根据需求转换为**GCJ-02(火星坐标系)**以配合国内导航应用。

    4.html

    4

Global site tag (gtag.js) - Google Analytics