回溯算法

class Solution {
    public boolean exist(char[][] board, String word) {
 // 二维网格的长和宽
        int h = board.length, w = board[0].length;
        // 设置一个二维数组用于标记节点是否被访问过
        boolean[][] visited = new boolean[h][w];
        // 对二维网格中的每个结点都进行搜索
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    // 在二维网格中判断board[i][j] 是否等于 s[k]
    public boolean check(char[][] board, boolean[][] visited, int x, int y, String word, int index) {
        // 如果搜索的点与字符串中的第k个字符不相同
        if (board[x][y] != word.charAt(index)) {
            return false;
        }
        // 整个字符串都已经找到了，返回true 
        else if (index == word.length() - 1) {
            return true;
        }
        // 访问结点，并继续搜索
        visited[x][y] = true;
        // 继续搜索的四个方向（上下左右）
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        // 用于标识接下来的搜索是否成功
        boolean result = false;
        for (int[] dir : directions) {
            int newx = x + dir[0], newy = y + dir[1];
            // 判断新坐标是否越界
            if (newx >= 0 && newx < board.length && newy >= 0 && newy < board[0].length) {
                if (!visited[newx][newy]) {
                    boolean flag = check(board, visited, newx, newy, word, index + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        // 回溯的返回过程
        visited[x][y] = false;
        return result;
    }
}