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

cblbrusvcm

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[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.length; j++) {
if (arrs[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[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;
}
}
}
}