【华为校招】【校招】【Java】单词搜索（DFS）

■ 题目描述
【单词搜索】
找到它是一个小游戏，你需要在一个矩阵中找到给定的单词。
假设给定单词 HELLOWORD，在矩阵中只要能找到 H->E->L->L->O->W->O->R->L->D连成的单词，就算通过。
注意区分英文字母大小写，并且您只能上下左右行走，不能走回头路。
输入描述
输入第 1 行包含两个整数 n、m (0 < n,m < 21) 分别表示 n 行 m 列的矩阵，
第 2 行是长度不超过100的单词 W (在整个矩阵中给定单词 W 只会出现一次)，
从第 3 行到第 n+2 行是指包含大小写英文字母的长度为 m 的字符串矩阵。
输出描述
如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置(第几行 第几列)，
否则输出“NO”。
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC
输出
3 2

public class WordSearch {

    public static int m,n;
    public static boolean find;
    public static void dfs(int i,int j,char[][] board, String word, boolean[][] visited,int pos){
        if (i<0||i>=m||j<0||j>=n||visited[i][j]||find||board[i][j]!=word.charAt(pos)){
            return;
        }
        if (pos==word.length()-1){
            find = true;
            return;
        }
        visited[i][j] = true;
        dfs(i+1,j,board,word,visited,pos+1);
        dfs(i,j+1,board,word,visited,pos+1);
        dfs(i-1,j,board,word,visited,pos+1);
        dfs(i,j-1,board,word,visited,pos+1);
        visited[i][j] = false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        sc.nextLine();
        String word = sc.nextLine();
        System.out.println("word:"+word);
        char[][] board = new char[m][n];
        for (int i=0;i<m;i++){
            String str = sc.nextLine();
            System.out.println(str);
            for (int j=0;j<n;j++){
                board[i][j] = str.charAt(j);
            }
        }

        boolean[][] visited = new boolean[m][n];
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (board[i][j] == word.charAt(0)) {
                    dfs(i, j, board, word, visited, 0);
                    if (find) {
                        System.out.print(i + 1);
                        System.out.print(" ");
                        System.out.print(j + 1);
                        return;
                    }
                }
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53