【剑指offer】面试题13：机器人的运动范围

浅浅的花香味﹌ 2022-06-12 07:38 139阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

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

## 思路 ##

这道题跟[面试题12：矩阵中的路径][12]的思路是差不多的，都是使用回溯法。  
用一个数组visited\[\]\[\]表示地上的方格是否已被访问过  
从起点(0, 0)开始，沿着路径（上下左右）走，每到一个符合条件的方格，数量就加1，并标识该方格已被访问过

## 代码 ##

public int movingCount(int threshold, int rows, int cols) {
        if(rows <= 0 || cols <= 0 || threshold < 0)
            return 0;
    
        boolean[][] visited = new boolean[rows][cols];
    
        return movingCount(threshold, rows, cols, 0, 0, visited);
    }
    
    private int movingCount(int threshold, int rows, int cols, int r, int c, boolean[][] visited) {
    
        if(r >= rows || r < 0 || c >= cols || c < 0)
            return 0;
        if(visited[r][c] || isBiggerThanThreshold(r, c, threshold))
            return 0;
    
        visited[r][c] = true;
    
        return 1 + movingCount(threshold, rows, cols, r + 1, c, visited) +
                movingCount(threshold, rows, cols, r - 1, c, visited) +
                movingCount(threshold, rows, cols, r, c + 1, visited) +
                movingCount(threshold, rows, cols, r, c - 1, visited);
    }
    
    private boolean isBiggerThanThreshold(int r, int c, int threshold) {
        int sum = 0;
        while(r > 0) {
            sum += r % 10;
            r /= 10;
        }
        while(c > 0) {
            sum += c % 10;
            c /= 10;
        }
        return sum > threshold;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
        test3();
    }
    
    /**
     * 功能测试
     * 0,0  0,1  0,2  0,3
     * 1,0  1,1  1,2  1,3
     * 2,0  2,1  2,2  2,3 
     */
    private static void test1() {
        _13_RobotMove rm = new _13_RobotMove();
        int res = rm.movingCount(3, 3, 4);
        MyTest.equal(res, 9);
    }
    
    /**
     * 边界值测试
     * 1.只有一行
     * 2.只有一列
     * 3.k等于0
     */
    private static void test2() {
        _13_RobotMove rm = new _13_RobotMove();
        // 0-9, 10-18
        int res = rm.movingCount(9, 30, 1);
        MyTest.equal(res, 19);
    
        // 0-9, 10-18
        res = rm.movingCount(9, 1, 30);
        MyTest.equal(res, 19);
    
        res = rm.movingCount(0, 2, 4);
        MyTest.equal(res, 1);
    }
    
    /**
     * 特殊输入测试
     */
    private static void test3() {
        _13_RobotMove rm = new _13_RobotMove();
        int res = rm.movingCount(-1, 4, 4);
        MyTest.equal(res, 0);
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews
[12]: http://blog.csdn.net/qq1263292336/article/details/75332404