题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

样例

注意：
输入的路径不为空
所有出现的字符均为大写英文字母；
样例
matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

算法1

(暴力枚举) $O(n^2*3^k)$

C++ 代码

class Solution {
public:
    int n, m; 
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size(), m = board[0].size();
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if( dfs(board, word, 0, i, j) ) return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>> &board, string &word, int u, int x, int y){
        if(board[x][y] != word[u]) return false;  //边界问题  当矩阵只有一个“a”时的情况
        if(u == word.size() - 1) return true;

        int dx[4] = {-1, 1, 0, 0};
        int dy[4] = {0, 0, -1, 1};
        char t = board[x][y];
        board[x][y] = '*';

        for(int i = 0; i < 4; ++i){
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if(x1 >= 0 && x1 < n && y1 >=0 && y1 < m && board[x1][y1] != '*'){
            // if(x1 >= 0 && x1 < n && y1 >=0 && y1 < m){
                if(dfs(board, word, u + 1, x1, y1)) return true; 
            }
        }
        board[x][y] = t;  //恢复现场
        return false;
    }
};