矩阵中的路径（dfs + 回溯 + 剪枝）

1.思路

对数组进行枚举看是否能够跟给定字符串的起点匹配，如果可以匹配的话，就以该点作为起点，进行DFS，由于数组中可能出现多个跟起点字符相同的字符，所以DFS访问过标记的结点需要取消标记，以便下次以其他起点进行搜索。

2.碰到的坑点

这道题目本来是一道基础的DFS题目，但是遇到了很多小问题，导致TLE，最后一个数据始终过不了。课了很长时间，去leetcode看了一下题解，突然顿悟。朴素的剪枝有 判断边界、判断当前状态合不合法、判断当前点是否被访问过。
但是像这道题，因为起点坐标可能在数组中多次出现，所以标记完之后需要取消标记，但是取消标记之后，即使找到了一条路径可以跟字符串匹配，但是DFS不会结束，会尝试下一条路径，遍历所有可能的解，即使不存在可能的解，还是会一直递归，直到找到出口，这样会使时间复杂度指数型增加。因此，在找到一个解之后立即结束，直接退出函数，避免多余的递归，消耗时间。

class Solution {
public:
    bool st[4000][4000];
    int flag =0;
    int rows,col;
    int dir[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
    void dfs(int x,int y,int step,vector<vector<char>>& matrix,string s)
    {

        if(step >= s.length())
        {
            flag = 1;
            return;
        }
        for(int i = 0;i<4;i++)
        {
            int dx = x + dir[i][0],dy = y + dir[i][1];
            if(dx < 0||dy<0||dx>= rows||dy>=col) continue;
            if(matrix[dx][dy] != s[step]||st[dx][dy]) continue;
            st[dx][dy] = 1;
            dfs(dx,dy,step + 1,matrix,s);
            st[dx][dy] = 0;
            if(flag == 1) return; //找到一个解就提前返回 如果不加的话最后一个样例过不去
        }
    }
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        if(matrix.empty()) return 0;
        rows  = matrix.size(),col = matrix[0].size();
        if(rows * col < str.length()) return 0;
        char start = str[0];
        int t = 0;
        for(int i = 0;i<rows;i++)
        {
            for(int j = 0;j<col;j++)
            {
                if(matrix[i][j] == start)
                {
                    flag = 0;
                    st[i][j] = 1;//新加入的起点也要标记
                    dfs(i,j,1,matrix,str);
                    if(flag == 1) return 1;
                    st[i][j] = 0;//新加入的起点也要标记
                }
            }
        }
        return 0;
    }
};