剑指 Offer 12. 矩阵中的路径

class Solution {
    
    int m, n, k;
    char[][] board; 
    char[] w;
    int[][] dirs = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};
    public boolean exist(char[][] board, String word) {
    
        m = board.length;
        n = board[0].length;
        k = word.length();
        this.board = board;
        w = word.toCharArray();
        
        for(int i = 0; i < m; i++){
    
            for(int j = 0; j < n; j++){
    
                if(board[i][j] == w[0]) {
           
                    board[i][j] = '!';
                    if(f(i, j, 1)) return true;
                    board[i][j] = w[0];
                }
            }
        }
        return false;
    }
    boolean f(int i, int j, int idx){
                   
        if(idx == k) return true;
        for(int[] dir : dirs){
    
            int x = i + dir[0];
            int y = j + dir[1];
            
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == w[idx]){
    
                board[x][y] = '!';
                if(f(x, y, idx + 1)) return true;
                board[x][y] = w[idx];
            }          
        }       
        return false;
    }
}