矩阵中的路径

回溯法：

//
// Created by jt on 2020/9/18.
//
#include <vector>
using namespace std;

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        vector<vector<int> > visited(rows, vector<int>(cols, 0));
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (backtrace(matrix, rows, cols, str, visited, i, j, 0)) return true;
            }
        }
        return false;
    }

    bool backtrace(char *matrix, int rows, int cols, char *str, vector<vector<int> > &visited, int x, int y, int pos) {
        if (x < 0 || x >= rows || y < 0 || y >= cols) return false;
        if (visited[x][y] || matrix[x*cols + y] != str[pos]) return false;
        if (pos == strlen(str) - 1) return true;
        visited[x][y] = 1;
        // 上
        bool a = backtrace(matrix, rows, cols, str, visited, x - 1, y, pos+1);
        // 下
        bool b = backtrace(matrix, rows, cols, str, visited, x + 1, y, pos+1);
        // 左
        bool c = backtrace(matrix, rows, cols, str, visited, x, y - 1, pos+1);
        // 右
        bool d = backtrace(matrix, rows, cols, str, visited, x, y + 1, pos+1);
        visited[x][y] = 0;
        return a || b || c || d;
    }
};