刷劍指offer也刷到最后了。也不知道能不能拿到好offer，現(xiàn)在一個還木有。不說那么多了，來看題。

請設計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子，則該路徑不能再進入該格子。 例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

說實話，一般題目很長的時候我就覺得要么是dp要么是圖里面的dfs／bfs。說回到這道題，那我們首先要做的就是在matrix里面找到一個元素和str[0]相等，這樣才能開始后面一系列的操作。那么這道題呢，這樣想。找到第一個元素之后我們就在他的周圍尋找和str[1]相等的元素。如果沒有的話，也就是只有這第一個元素匹配，那說明這個位置的str[0]不能用，我們需要重新找開始的地點。把這種思想往遞歸里想，當我們找到第一個匹配的時候，我們就在這個附近尋找，接下來的匹配。一個一個的試，如果符合就在這個新的元素的附近去匹配下一個元素，如果有匹配的話就遞歸的去試，如果遍歷這個元素周圍的所有的元素都沒有合適的，那說明這個元素不應該出現(xiàn)在路徑中，我們需要把這個元素刪掉。所以發(fā)現(xiàn)沒有這就是一個dfs算法，如果要保存的路徑的話我們需要使用一個stack，但是現(xiàn)在不需要，所以就不使用。

代碼：

class Solution
{
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix==nullptr||rows<1||cols<1||str==nullptr)
            return false;
        bool * visited = new bool[rows*cols];
        memset(visited,0,rows*cols);
        int pathLength=0;
        for(int row = 0;row<rows;++row)
        {
            for(int col = 0;col<cols;++col)
            {
                if(hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited))
                    return true;
            }
        }
        delete[] visited;
        return false;
    }

    bool hasPathCore(const char* matrix,int rows,int cols,const char* str,int& pathLength,bool* visited)
    {
        if(str[pathLength]=='\0')
            return true;
        bool hasPath=false;
        if(row>=0&&row<rows&&col>=0&&col<cols&&str[pathLength]==matrix[row*cols+col]&&!visited[row*cols+col])
        {
            ++pathLength;
            visited[row*cols+col] = true;
            hasPath = hasPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited)
                ||hasPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited)
                ||hasPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited)
                ||hasPathCore(matrix,rows,cols,row+1,col,str,pathLength,visited);
            if(!hasPath)
            {
                --pathLength;
                visited[row*cols+col];
            }
        }
        return hasPath;
    }
}