剑指offer--在矩阵中找路径

题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如[a b c e s f c s a d e e]是3*4矩阵，其包含字符串"bcced"的路径，但是矩阵中不包含“abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

典型的回溯题, 代码可当作模版

//
//  s_66.cpp
//  swordOffer
//
//  Created by YangKi on 2017/3/14.
//  Copyright © 2017年 yangqi916. All rights reserved.
//

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

class Solution {
    
    bool findCore(char* matrix, int rows, int cols, char* str, int curRow, int curCol, int& pathLength, vector<vector<bool>>& visited) {
        if(str[pathLength] == '\0')
            return true;
        
        bool hasPath = false;
        
        if(curRow >= 0 && curRow < rows
           && curCol >= 0 && curCol < cols
           && str[pathLength] == matrix[curRow*cols + curCol]
           && visited[curRow][curCol] == false)
        {
            visited[curRow][curCol] = true;
            pathLength++;
            
            if (findCore(matrix, rows, cols, str, curRow + 1, curCol, pathLength, visited)
                || findCore(matrix, rows, cols, str, curRow - 1, curCol, pathLength, visited)
                || findCore(matrix, rows, cols, str, curRow, curCol + 1, pathLength, visited)
                || findCore(matrix, rows, cols, str, curRow, curCol - 1, pathLength, visited))
            {
                hasPath = true;
            }
            
            visited[curRow][curCol] = false;
            pathLength--;
        }
        
        return hasPath;
    }
    
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
            return false;
        
        vector<vector<bool>>visited(rows, vector<bool>(cols, false));
        
        int pathLength = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (findCore(matrix, rows, cols, str, i, j, pathLength, visited))
                    return true;
            }
        }
        
        return false;
    }
    
};