题解 | #矩阵中的路径#

#include <string>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型vector<vector<>>
     * @param word string字符串
     * @return bool布尔型
     */
    bool findpath = false;
    void helper(vector<vector<char> >& land, vector<vector<char> >& map,
                string curstr, string word, int x, int y, int num) {
        if (findpath) return; //已经找到路径 直接返回
        if (num >= word.size()) { //这条路径搜索完成 返回
            if (curstr == word) { //找到路径 返回
                // cout<<curstr<<endl;
                findpath = true;
                //cout<<curstr<<endl;
                return;
            }
            return;
        }
        if (num>1&&curstr[num-1]!=word[num-1])
            return;

        if ( x < 0 || y < 0 || x >= map.size() || y >= map[0].size())
            return;
        if (map[x][y]) //以前来过这个位置 返回
            return;

        map[x][y] = 1;
        //继续搜索
        //向上
        //curstr.push_back(land[x][y]);
        helper( land, map, curstr+land[x][y], word,  x - 1, y, num + 1);
        //向下
        helper(land, map, curstr+land[x][y], word,  x + 1, y, num + 1);
        //向左
        helper( land, map, curstr+land[x][y], word,  x, y - 1, num + 1);
        //向右
        helper( land, map, curstr+land[x][y], word,  x, y + 1, num + 1);
        //curstr.pop_back();
        map[x][y] = 0;
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if (matrix.size() == 0)return false;
        if (matrix[0].size() == 0)return false;
        int row = matrix.size(), col = matrix[0].size();
        vector<vector<char> > map (row, vector<char>(col, 0));
        string cur = "";

        for (int x = 0; x < matrix.size() ; ++x)
            for (int y = 0; y < matrix[0].size() ; ++y) {
                helper(matrix, map,  cur, word, x, y, 0);
                if(findpath) break;
            }

        return findpath;

    }
};