题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int n,m;
    int go[4][2]={0,1,1,0,0,-1,-1,0};//方向数组，即上下左右
    int k;//遍历到str的第k个字符
    int f[1000][1000];//标志数组，判断该点是否遍历过；为0则没有遍历，1为遍历过
    bool b=false;
    bool dfs(vector<vector<char>> matrix,string str,int h,int l) {
        if(k==str.length()) b=true;//k到str字符串的尾部，则说明前k个字符已匹配；
        if(k<str.length()) {
            for(int i=0;i<4;i++){
                int nx=h+go[i][0];//上下左右四个方向；
                int ny=l+go[i][1];
                if(nx<0||ny<0||ny>=m||nx>=n) continue;//超出边界
                if(matrix[nx][ny]==str[k]&&f[nx][ny]==0&&k<str.length()){//符合str匹配的字符
                    k++;f[nx][ny]=1;
                    b=dfs(matrix,str,nx,ny);
                    f[nx][ny]=0;
                }
            }
        }
        return b;
    }
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        if(!matrix.size()||!matrix[0].size()) return false;
        n=matrix.size();
        m=matrix[0].size();
        if(n*m<str.length()) return false;//matrix数组长度小于str长度
        int i,j;
        k=0;
        bool bb=false;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
                if(matrix[i][j]==str[k])
                {
                    f[i][j]=1;k++;
                    bb=dfs(matrix,str,i,j);
                    if(bb==true) return true;//返回true，则找到路径
                    f[i][j]=0;
                }
        }
        return false;
    }
};