算法：DFS+剪枝+回溯

这道题是很经典的DFS问题，走迷宫的变种，需要注意递归边界和矩阵边界。

时间复杂度

$O(N^2·3^k)$, k为平均路径长度。

代码

class Solution {
public:
    vector<vector<bool>> vis;
    int m, n;
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() == 0) return true;
        m = board.size();
        n = board[0].size();
        vis.resize(m, vector<bool>(n));
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                if(dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int u){
        if(board[i][j] != word[u]){
            return false;
        }
        if(u == word.size()-1){ // 递归边界
            return true;
        }
        vis[i][j] = true;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for(int k = 0; k < 4; k ++){
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]){ // 矩阵边界
                if(dfs(board, word, x, y, u + 1)) return true;
            }
        }
        vis[i][j] = false;

        return false;
    }
};