题解 | #矩阵中的路径#

import java.util.*;


class Solution {
    public boolean hasPath(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    visited[i][j] = true;
                    if (dfs(board, word, visited, 1, i, j)) {
                        return true;
                    }
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, boolean[][] visited, int k, int x, int y) {
        if (k == word.length()) {
            return true;
        }
        if (x + 1 < board.length && (!visited[x + 1][y]) && word.charAt(k) == board[x + 1][y]) {
            visited[x + 1][y] = true;
            if (dfs(board, word, visited, k + 1, x + 1, y)) {
                visited[x + 1][y] = false;
                return true;
            }
            visited[x + 1][y] = false;
        }
        if (x - 1 > -1 && (!visited[x - 1][y]) && word.charAt(k) == board[x - 1][y]) {
            visited[x - 1][y] = true;
            if (dfs(board, word, visited, k + 1, x - 1, y)) {
                visited[x - 1][y] = false;
                return true;
            }
            visited[x - 1][y] = false;
        }
        if (y + 1 < board[0].length && (!visited[x][y + 1]) && word.charAt(k) == board[x][y + 1]) {
            visited[x][y + 1] = true;
            if (dfs(board, word, visited, k + 1, x, y + 1)) {
                visited[x][y + 1] = false;
                return true;
            }
            visited[x][y + 1] = false;
        }
        if (y - 1 > -1 && (!visited[x][y - 1]) && word.charAt(k) == board[x][y - 1]) {
            visited[x][y - 1] = true;
            if (dfs(board, word, visited, k + 1, x, y - 1)) {
                visited[x][y - 1] = false;
                return true;
            }
            visited[x][y - 1] = false;
        }
        return false;
    }
}