华为OD机试真题 - 找单词
static int[][] DISTANCE = {{1,0},{-1,0},{0,1},{0,-1}};
static String ans = null;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = Integer.parseInt(in.nextLine());
String[][] ch = new String[num][num];
for (int i = 0; i < num; i++) {
ch[i] = in.nextLine().split(",");
}
String word = in.nextLine();
System.out.println(word);
getResult(word, ch);
}
public static void getResult(String word, String[][] map) {
boolean[][] visited = new boolean[map.length][map.length];
StringBuilder out = null;
String path = "";
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
out = new StringBuilder();
dfs(word, visited, map, i, j, out, 0, path);
}
}
System.out.println(ans);
}
public static boolean dfs(String word, boolean[][] visited, String[][] map, int i, int j, StringBuilder out, int depth, String path) {
if (word.equals(path)) {
ans = out.delete(out.length() - 1, out.length()).toString();
return true;
}
if (i >= map.length || j >= map.length || i < 0 || j < 0)
return false;
if (visited[i][j] == true)
return false;
if (word.charAt(depth) != map[i][j].charAt(0))
return false;
visited[i][j] = true;
out.append(i + ",");
out.append(j + ",");
for (int k = 0; k < DISTANCE.length; k++) {
if(dfs(word, visited, map, i + DISTANCE[k][0], j + DISTANCE[k][1], out, depth + 1, path + map[i][j]))
return true;
}
out.delete(out.length() - 4, out.length());
visited[i][j] = false;
return false;
}
static String ans = null;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = Integer.parseInt(in.nextLine());
String[][] ch = new String[num][num];
for (int i = 0; i < num; i++) {
ch[i] = in.nextLine().split(",");
}
String word = in.nextLine();
System.out.println(word);
getResult(word, ch);
}
public static void getResult(String word, String[][] map) {
boolean[][] visited = new boolean[map.length][map.length];
StringBuilder out = null;
String path = "";
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
out = new StringBuilder();
dfs(word, visited, map, i, j, out, 0, path);
}
}
System.out.println(ans);
}
public static boolean dfs(String word, boolean[][] visited, String[][] map, int i, int j, StringBuilder out, int depth, String path) {
if (word.equals(path)) {
ans = out.delete(out.length() - 1, out.length()).toString();
return true;
}
if (i >= map.length || j >= map.length || i < 0 || j < 0)
return false;
if (visited[i][j] == true)
return false;
if (word.charAt(depth) != map[i][j].charAt(0))
return false;
visited[i][j] = true;
out.append(i + ",");
out.append(j + ",");
for (int k = 0; k < DISTANCE.length; k++) {
if(dfs(word, visited, map, i + DISTANCE[k][0], j + DISTANCE[k][1], out, depth + 1, path + map[i][j]))
return true;
}
out.delete(out.length() - 4, out.length());
visited[i][j] = false;
return false;
}
全部评论
相关推荐
点赞 评论 收藏
分享