一个暴搜模板题

1. 先判断第一个字母是否相同,然后标记,开始进行dfs
2. 写出口,当str被遍历完了,退出
3. 枚举四个方向,然后排除不符合条件的选项
4. 打上标记,深搜,恢复现场

const int N = 1010;
class Solution {
public:
    bool st[N][N];
    int n,m;
    string str;
    bool dfs(int x, int y,int u, vector<vector<char>> & matrix)
    {
        if(u == str.size())return true;
        int dx[] = { 1,0,-1,0},dy[]= {0,-1,0,1};
        for(int i = 0; i< 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >=m)continue;
            if(st[nx][ny])continue;
            if(matrix[nx][ny] != str[u])continue;

            st[nx][ny] = 1;
            if(dfs(nx,ny,u + 1, matrix))return true;
            st[nx][ny] = 0;
        }
        return false;
    }
    bool hasPath(vector<vector<char>>& matrix, string &s) {
            if(matrix.empty())return false;
            n = matrix.size();
            m = matrix[0].size();
            str = s;
            for(int i = 0; i < n; i ++)
                for(int j = 0; j < m; j++)
                {
                    if(matrix[i][j] == str[0])
                    {
                        st[i][j] = 1;
                        if(dfs(i,j,1,matrix))return true;
                        st[i][j] = 0;
                    }
                }
        return false;
    }
};