5/22刷题

1.矩阵中的路径

思路：回溯

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);//visit矩阵都设为零
        int pathLength=0;//字符串计数
        for(int row=0;row<rows;++row)
        {
            for(int col=0;col<cols;++col)
            {
                if(hashPathCore(matrix,rows,cols,row,col,str,pathLength,visited))
                {
                    return true;
                }
            }
        }
        delete[] visited;
        return false;
    }
    //回溯算法
    bool hashPathCore(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])
        {
        ++pathLength;//如果row，col点符合要求，那么pathLength加一
        visited[row*cols+col]=true;//标记走过了
        hasPath=hashPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited)||
            hashPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited)||
            hashPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited)||
            hashPathCore(matrix,rows,cols,row+1,col,str,pathLength,visited);
       //如果row，col点和pathlength是一致的，那么就从他的上下左右找符合pathlength+1的字符
        if(!hasPath)
        {
            --pathLength;
            visited[row*cols+col]=false;//如果不符合要求，回溯到上一点，把visited重置
        }
        }
        return hasPath;
    }
};

2.机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<0||rows<=0||cols<=0)
            return 0;//特殊情况
        vector<bool> visited(rows*cols,false);
        int count=Count(threshold,0,0,rows,cols,visited);
        return count;
    }
    int Count(int threshold,int row,int col,int rows,int cols,vector<bool>& visited)
    {
        int count=0;
        if(check(threshold,row,col,rows,cols,visited))
        {
            visited[row*cols+col]=true;
            count=1+Count(threshold,row+1,col,rows,cols,visited)+
                Count(threshold,row,col+1,rows,cols,visited)+
                Count(threshold,row-1,col,rows,cols,visited)+
                Count(threshold,row,col-1,rows,cols,visited);
        }
        return count;
    }
    bool check(int threshold,int row,int col,int rows,int cols,vector<bool>& visited)
    {
        if(row>=0&&row<rows&&col>=0&&col<cols&&!visited[row*cols+col]&&
          Sum(row)+Sum(col)<=threshold)
            return true;
        return false;
    }
    int Sum(int number)
    {
        int sum=0;
        while(number>0)
        {
            sum+=number%10;
            number/=10;
        }
        return sum;
    }
};