题解 | #童谣寻找问题#

知识点：dfs

思路：模拟迷宫，dfs寻找，我们需要添加额外的 visited 数组来记录访问过的元素，以避免重复访问。注意 Java 中的数组索引范围为 0 到 length-1，因此循环条件需要进行相应的调整

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, -1, 0, 1};

    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;

        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, String word, boolean[][] visited, int x,
                        int y, int index) {
        if (index == word.length()) {
            return true;
        }

        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length ||
                visited[x][y] || board[x][y] != word.charAt(index)) {
            return false;
        }

        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (dfs(board, word, visited, nx, ny, index + 1)) {
                return true;
            }
        }

        visited[x][y] = false;
        return false;
    }
}