矩阵中的路径

题解方法

• 深度优先搜索

深度优先搜索

• 任意位置均可作为搜索的起点

终止条件

• 数组越界
• 当前位置已访问
• 当前字符与目标字符不匹配

匹配条件

• 当前递归次数等于目标字符串长度

搜索步骤

• 标记当前位置为已访问
• 递归次数自增
• 向当前位置的四个方向继续搜索
• 回溯，标记当前位置为未访问

核心代码

深度优先搜索

private boolean dfs(int i, int j, int idx) {
    // 如果数组越界、当前位置已访问或当前字符与目标字符不匹配，返回 false
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(idx)) {
        return false;
    }
    // 递归次数等于目标字符串长度，说明已经匹配到最后一个字符
    if (idx == word.length() - 1) {
        return true;
    }
    // 标记当前位置已访问
    visited[i][j] = true;
    idx++;
    // 向当前位置的四个方向继续搜索，只要有一个方向能匹配到，就返回 true
    boolean res = dfs(i + 1, j, idx) || dfs(i - 1, j, idx) || dfs(i, j + 1, idx) || dfs(i, j - 1, idx);
    // 回溯，将当前位置标记为未访问
    visited[i][j] = false;

    return res;
}

题目来源

剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode）