面试题13:机器人的运动范围

题目

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

解题思路

1. 明白题目含义:行坐标和列坐标的数位之和大于k的格子，即这道题是针对矩阵坐标而非矩阵中的值。
2. 采用回溯法解决。

• 机器人有回退行为
  如果k=1,机器人能到达的格子为(0,0)-->(0,1)和(0,0)-->(1,0)两种方式。也就是说当机器人走到(0,1)时可以回退到(0,0)再继续找到(1,0)。
  当行和列为5，k = 3时经过的格子图(用以理解下面的递归代码)

  
  image.png

• 机器人无回退行为
  同上，只能找到一条路径能到达的格子为(0,0)-->(0,1)或(0,0)-->(1,0)

代码

• 一维数组存储二维数据(有回退行为的)
  每到达一个格子，就判断该格子的上下左右的格子是否满足条件。把每个方向能到达的格子数a[i]记录下来并相加

class Solution{
  public:
    int add_row_col(int loc)
    {
        int tt = 0;
        while(loc>0)
        {
            tt += loc%10;
            loc /= 10;
        }
        return tt;
    }
    
    int movingCountCore(int threshold,int row,int col,int rows,int cols,int *visited)
    {
        int a[4];
        int result = 0;
        memset(a,0,4*sizeof(int));
        if(visited[row*cols+col]==0 && add_row_col(row) + add_row_col(col) <= threshold)
        {
            visited[row*cols + col] = 1;
            
            //向上找
            if(row>0 )
            {
                a[0] = movingCountCore(threshold,row-1,col,rows,cols,visited);
            }
            //下
            if(row < rows-1 )
            {
                a[1] = movingCountCore(threshold,row+1,col,rows,cols,visited);
            }

            //左

            if(col > 0)
            {
                a[2] = movingCountCore(threshold,row,col-1,rows,cols,visited);
            }
            //右

            if(col < cols-1)
            {
                a[3] = movingCountCore(threshold,row,col+1,rows,cols,visited);
            }
            
            result = 1+a[0]+a[1]+a[2]+a[3];
            //cout << "result: " << result << endl;
        }
        else
        {
            result = 0;
        }

        cout << "result: " << result << endl;
        return result;
    }

    int movingCount(int threshold,int rows,int cols)
    {
        if(threshold < 0 || rows <= 0 || cols <= 0 )
        {
            return 0;
        }
        int visited[rows*cols]; //标识路径是否已进入每个格子
        memset(visited,0,sizeof(int)*rows*cols);
        return movingCountCore(threshold,0,0,rows,cols,visited);
    }
};

• 二维数组存储二维数据(有回退行为的)
• 细节
  定义全局变量

#define rows 4
#define cols 4
#define threshold 2

class Solution{
  public:
    int add_row_col(int loc)
    {
        int tt = 0;
        while(loc>0)
        {
            tt += loc%10;
            loc /= 10;
        }
        return tt;
    }
    
    int movingCountCore(int row,int col,int visited[][cols])
    {
        int a[4];
        int result = 0;
        memset(a,0,4*sizeof(int));
        if(visited[row][col]==0 && add_row_col(row) + add_row_col(col) <= threshold)
        {
            visited[row][col] = 1;
            
            //向上找
            if(row>0 )
            {
                a[0] = movingCountCore(row-1,col,visited);
            }
            //下
            if(row < rows-1 )
            {
                a[1] = movingCountCore(row+1,col,visited);
            }

            //左

            if(col > 0)
            {
                a[2] = movingCountCore(row,col-1,visited);
            }
            //右

            if(col < cols-1)
            {
                a[3] = movingCountCore(row,col+1,visited);
            }
            
            result = 1+a[0]+a[1]+a[2]+a[3];
            //cout << "result: " << result << endl;
        }
        else
        {
            result = 0;
        }

        cout << "result: " << result << endl;
        return result;
    }

    int movingCount()
    {
        if(threshold < 0 || rows <= 0 || cols <= 0 )
        {
            return 0;
        }
        int visited[rows][cols]; //标识路径是否已进入每个格子
        memset(visited,0,sizeof(int)*rows*cols);
        return movingCountCore(0,0,visited);
    }
};

• 一维数组存储二维数据(无回退行为的)
  找到每个格子上下左右能到达的格子数a[i]，然后比较哪个方向的格子数最多，就把result= max(a[0],a[1],a[2],a[3]).

class Solution{
  public:
    int add_row_col(int loc)
    {
        int tt = 0;
        while(loc>0)
        {
            tt += loc%10;
            loc /= 10;
        }
        return tt;
    }
    
    int movingCountCore(int threshold,int row,int col,int rows,int cols,int *visited)
    {
        int a[4];
        int result = 0;
        memset(a,0,4*sizeof(int));
        if(visited[row*cols+col]==0 && add_row_col(row) + add_row_col(col) <= threshold)
        {
            visited[row*cols + col] = 1;
            
            //向上找
            if(row>0 )
            {
                a[0] = movingCountCore(threshold,row-1,col,rows,cols,visited);
            }
            //下
            if(row < rows-1 )
            {
                a[1] = movingCountCore(threshold,row+1,col,rows,cols,visited);
            }

            //左

            if(col > 0)
            {
                a[2] = movingCountCore(threshold,row,col-1,rows,cols,visited);
            }
            //右

            if(col < cols-1)
            {
                a[3] = movingCountCore(threshold,row,col+1,rows,cols,visited);
            }
            
            //result = 1+a[0]+a[1]+a[2]+a[3];
            //无回退行为
            for(int i=0;i<4;i++)
            {
                if(result < a[i])
                {
                    result = a[i];
                }
            }
            result +=1;
            //cout << "result: " << result << endl;
        }
        else
        {
            result = 0;
        }

        cout << "result: " << result << endl;
        return result;
    }

    int movingCount(int threshold,int rows,int cols)
    {
        if(threshold < 0 || rows <= 0 || cols <= 0 )
        {
            return 0;
        }
        int visited[rows*cols]; //标识路径是否已进入每个格子
        memset(visited,0,sizeof(int)*rows*cols);
        return movingCountCore(threshold,0,0,rows,cols,visited);
    }
};

总结

建议使用一维数组的方式，这样的时间复杂度更低，效率更高。当机器人无回退行为时，和面试题47:礼物的最大价值就是同一个类型的。

完整代码见Github