美文网首页
面试题13: 机器人移动范围

面试题13: 机器人移动范围

作者: mark_x | 来源:发表于2019-10-10 01:02 被阅读0次
    package cn.zxy.interview;
    
    import org.junit.Test;
    
    /**
     * 题目:机器人的运动范围: 地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移
     * 动,每一次只能往左右上下四个方向移动一格,但是不能进入行坐标和列坐
     * 标的数位之和大于k的格子。请问该机器人能够达到多少个格子?
     *
     * 分析: 到达格子A, 如果A满足条件, 计算可移动的四个方向上每个方向可以到达多少个格子
     * 如果不满足条件, 直接返回
     * 使用递归实现, 进入一个格子, 只要这个格子满足条件, 就可以往下递归
     */
    
    public class A13_RangOfRobot {
        public static int movingCount(int threshold, int rows, int cols){
            int[][] visited = new int[rows][cols];  //记录是否走过
            int count = countCore(0, 0, rows, cols, visited, threshold);
            return count;
        }
    
        private static int countCore(int i, int j, int rows, int cols, int[][] visited, int threshold) {
            if(i < 0 || i >= rows || j < 0 || j >= cols ||
                    numSum(i)+numSum(j) > threshold || visited[i][j] == 1){
                // 该格子不能进入
                return 0;
            }
            // 标记已访问
            visited[i][j] = 1;
            System.out.println("(" + i + "," + j + ")");
    
            return 1 + countCore(i-1, j, rows, cols, visited, threshold)
                     + countCore(i+1, j, rows, cols, visited, threshold)
                     + countCore(i, j-1, rows, cols, visited, threshold)
                     + countCore(i, j+1, rows, cols, visited, threshold);
        }
    
    
        private static int numSum(int num) {
            int sum = 0;
            int temp = num;
            while(temp > 0){
                sum += temp % 10;
                temp /= 10;
            }
            return sum;
        }
    
    
        public static void main(String[] args) {
            System.out.println(movingCount(5, 10, 10));
        }
    }
    
    
    

    相关文章

      网友评论

          本文标题:面试题13: 机器人移动范围

          本文链接:https://www.haomeiwen.com/subject/hlnnpctx.html