🌕 剑指 Offer 12. 矩阵中的路径

难度: 🌕

问题描述

---

解法

class Solution {
    int row;
    int col;
    int len;
    public boolean exist(char[][] board, String word) {
        // 思路：
        // 回溯
        row = board.length;
        col = board[0].length;
        len = word.length();
        char exp = word.charAt(0);
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(board[i][j] == exp) {
                    if(mySol(board, word, 0, i, j)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean mySol(char[][] board, String word, int index, int i, int j) {
        // 递归终止条件
        if(index == len) {
            return true;
        }
        if(!isValid(i, j)) {
            return false;
        }
        char c = board[i][j];
        char exp = word.charAt(index);
        if(c != exp) {
            return false;
        }
        board[i][j] = '#'; // 染色，防止走了已经走过的路径
        boolean res = mySol(board, word, index + 1, i - 1, j) ||
                      mySol(board, word, index + 1, i + 1, j) ||
                      mySol(board, word, index + 1, i, j - 1) ||
                      mySol(board, word, index + 1, i, j + 1);
        if(res) {
            return true;
        }
        board[i][j] = c;
        return false;
    }

    private boolean isValid(int i, int j) {
        if(i < 0 || j < 0) {
            return false;
        }
        if(i >= row || j >= col) {
            return false;
        }
        return true;
    }
}

---

输出