【上海校区】算法题(二十):机器人的活动范围问题

python 未结 0 247
重庆网站优化
重庆网站优化 2021-07-22 15:25
悬赏:12
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

分析
1. 要判断四个方向是否可以继续前进,需要一个记录各个位置是否可以访问的一维数组;

2. 可以用深度优先算法遍历二维数组,遍历过程中将遍历过的格子设置成已访问状态(true);

代码
public class RobortRegion {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int rows = 3;
                int cols = 3;
                int threshold = 3;
                System.out.println(movingCount(threshold, rows, cols));
        }
       
        public static int movingCount(int threshold, int rows, int cols){
                boolean[] flag = new boolean[rows*cols];
                int res = moving(threshold, rows, cols, 0, 0, flag);
                return res;
        }
       
        //深度优先遍历矩阵
        public static int moving(int threshold, int rows, int cols, int i, int j, boolean[] flag){
                int res = 0;
                if(check(threshold, rows, cols, i, j, flag)){
                        flag[i*rows+j] = true;
                        res = 1+moving(threshold, rows, cols, i+1, j, flag)+
                                        moving(threshold, rows, cols, i-1, j, flag)+
                                        moving(threshold, rows, cols, i, j+1, flag)+
                                        moving(threshold, rows, cols, i, j-1, flag);
                }
                return res;
        }
       
        //检查位置是否可访问
        public static boolean check(int threshold, int rows, int cols, int i, int j, boolean[] flag){
                if(0<=i && i<rows && j>=0 && j<cols &&
                                getSum(i)+getSum(j)<=threshold &&
                                flag[i*rows+j]==false){
                        return true;
                }
                return false;
        }
       
        //得到位置(i,j)上的和(分开计算i,j)
        public static int getSum(int num){
                int res = 0;
                while(num>0){
                        res += num%10;
                        num /= 10;
                }
                return res;
        }

}

---------------------
作者:另一个我竟然存在
来源:CSDN
原文:https://blog.csdn.net/qq_24034545/article/details/83513117
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复