华为上机题之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;
int i = 0;
while (cin.hasNext()) {
String temp = cin.next();
for (int j = 0; j < temp.length(); j++) {
arrs = 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.length; j++) {
if (arrs == 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 != 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;
}
}
}
}
页:
[1]