剑指Offer-机器人的运动范围

小鱼儿 2022-02-04 01:23 207阅读 0赞

## 题目描述 ##

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

解题思路—**递归**：`这题可以抽象成找出以(0,0)为起点的所有<=threshold的连通结点。`**因为题目要求从0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，你肯定会想到用回溯法，但是这题与回溯法有本质上的区别，本题从(0,0)开始只需要往右以及往下，沿这两个方向遍历就能遍历完整个数组，所以并不需要回退。**（**回溯法**经典参考题型：**[剑指Offer-矩阵中的路径][Offer-]**，可以先看懂回溯法，再来理解这题会很容易。）解题的时候依旧要生成一个**标志位数组**来标识当前结点有没有遍历过，最后**返回所有遍历经过的连通结点的总和**即可。  
解题思路—**非递归堆栈**：核心思想与递归一样，只不过**使用堆栈同步存储已经遍历过的结点**进行判断。

## Java解题—递归 ##

public class Solution {
        public int movingCount(int threshold, int rows, int cols)
        {
            if(threshold<0 || rows<0 || cols<0)
                return 0;
            boolean[][] isWalk = new boolean[rows][cols];
            return cal(threshold, rows, cols, isWalk, 0, 0);
        }
        
        public int cal(int threshold, int rows, int cols, boolean[][] isWalk, int i, int j){
            if (i>=rows || j>=cols || isWalk[i][j] || bitSum(i)+bitSum(j)>threshold)
                return 0;
    
            isWalk[i][j] = true;
    
            return cal(threshold, rows, cols, isWalk, i+1, j) 
                    + cal(threshold, rows, cols, isWalk, i, j+1) 
                    + 1;
        }
        
        // 计算行列值
        public int bitSum(int x){
            int num = 0;
            while(x!=0){
                num += x%10;
                x /= 10;
            }
            return num;
        }
    }

## Java解题—非递归堆栈 ##

import java.util.Stack;
    public class Solution {
        public int movingCount(int threshold, int rows, int cols)
        {
            if(threshold<0 || rows<=0 || cols<=0)
                return 0;
            boolean[] isWalk = new boolean[rows*cols];
            Stack<Integer> stack = new Stack<>();
            int cal = 0;
            stack.push(0);
            isWalk[0] = true;
            // 往右下遍历
            int[] x = {1, 0};
            int[] y = {0, 1};
    
            while(!stack.isEmpty()){
                int curloc = stack.pop();
                cal++;
    
                for(int i=0;i<2;i++){
                    int xn = curloc/cols + x[i];
                    int yn = curloc%cols + y[i];
                    int sum = bitSum(xn) + bitSum(yn);
                    if(xn<rows && yn<cols && sum<=threshold && !isWalk[xn*cols+yn]){
                        stack.push(xn*cols+yn);
                        isWalk[xn*cols+yn] = true;
                    }
                }
            }
            return cal;
        }
        
        public int bitSum(int x){
            int num = 0;
            while(x!=0){
                num += x%10;
                x /= 10;
            }
            return num;
        }
    }

[Offer-]: https://blog.csdn.net/gaoyueace/article/details/89875829