劍指Offer(牛客版)--面試題12：矩陣中的路徑

題目：請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字元串所有字元的路徑。路徑可以從矩陣中任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經過了矩陣的某一格，那麼該路徑不能再次進入該格子。例如在下面的3×4的矩陣中包含一條字元串"bfce”的路徑（路徑中的字母用下劃線标出）。但矩陣中不包含字元串"abfb”的路徑，因為字元串的第一個字元b占據了矩陣中的第一行第二個格子之後，路徑不能再次進入這個格子

完整代碼：

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        //檢查輸入的合法性
        if(matrix==nullptr ||rows<1 ||cols<1 ||str==nullptr)
          return false;
        
        //定義一個布爾矩陣，其大小和matrix一樣，用來存放元素有沒有通路過的辨別
        bool *Visited =new bool [rows*cols];
        //用來初始化矩陣Visited所有元素即為0，即為false
        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))
                {
                    //删除輔助數組
                    delete[] Visited;
                    //傳回比對成功
                    return true;
                }
            }
        }
        //釋放輔助空間
        delete[] Visited;
        //運作至此，說明比對失敗
        return false;
    }
private:
     //調用比對函數，從矩陣上的每一個點開始嘗試比對
     bool hasPathCore(const char* matrix,int rows,int cols,int row,int col, const char* str,int&Pathlength,bool* Visited)
     {
     //如果已經比對完整個字元序列，到結尾了
      if(str[Pathlength]=='\0')
           return true; //直接傳回true，表示已經比對完整個字元串
      //記錄該元素是否已經比對過
       bool hasPath=false;
      //如果遊标在合法範圍内，且這個位置的值正好比對，而且沒有通路過
      if(row>=0&&row<rows&&col>=0&&col<cols&&matrix[row*cols+col]==str[Pathlength]&&!Visited[row*cols+col])
       {
          //路徑向前+1
           ++Pathlength;
          //表示已經通路過
           Visited[row*cols+col]=true;
          //繼續向前周遊,調用自身，分别從左/右/上/下比對，隻要有一個比對成功，立即結束
           hasPath=hasPathCore(matrix,rows,cols,row-1,col,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,col+1,str,Pathlength,Visited);
                     
           //如果四個方向不存在比對的字元，說明這個位置走錯
            if(!hasPath)
            {
               //先後倒退一步
                --Pathlength;
                Visited[row*cols+col]=false;
            }
         }
         //傳回這個位置是否比對過
          return  hasPath;
     }
};