华为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(&quot;,&quot;);
        }
        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 = &quot;&quot;;
        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 + &quot;,&quot;);
        out.append(j + &quot;,&quot;);
        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;
    }