【剑指 Offer】12. 矩阵中的路径

[sayid760]

原址

[sayid760]

深搜+回溯，深搜的过程其实就是对四个方向的一个递归调用的过程，回溯的话是为了消除某一次递归调用所产生的路径不能匹配模式串所产生的影响要被消除掉，消除的结果就是对这条路径上的每一个位置进行状态初始化，即标记为未被遍历

• 在矩阵中找字符串，从起点位置i,j出发，看能不能找到与word相匹配的字符串
• 左右上下都可以走，表示题可以x+1（往下走），x-1（往上走），y+1（往右走），y-1（往左走）入手，四个坐标的变化
• 矩阵只遍历一次，已经遍历过的不再遍历，二维数组做布尔值vis[x][y]为true的表示已经遍历过，下次不能再遍历，false表示没有遍历
• 并不是每次枚举就能找到匹配的值，所以要初始化状态

var solve = (board, word, x, y, vis, index) =>{
    // 越界处理以及每个方格只能访问一次
    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || vis[x][y]) {
        return false;
    }
    // 匹配到某一位置不满足条件
    if (word.charAt(index) != board[x][y]) {
        return false;
    }
    // 匹配成功
    if (index == word.length - 1) {
        return true;
    }
    vis[x][y] = true; // x，y位置的标记
    let flag = solve(board, word, x + 1, y, vis, index + 1) ||
                    solve(board, word, x - 1, y, vis, index + 1) ||
                    solve(board, word, x, y + 1, vis, index + 1) ||
                    solve(board, word, x, y - 1, vis, index + 1);
    // 初始化
    vis[x][y] = false; // x，y位置的标记状态回溯
    return flag;
}

var exist = function(board, word) {
    let vis = Array.from({length: board.length},()=> new Array(board[0].length).fill(0));
    console.log(vis)
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {
            if (solve(board, word, i, j, vis, 0)) {
                // 找到一种情况即可
                return true;
            }
        }
    }
    return false;
};