【上海校区】算法题（二十）：机器人的活动范围问题

题目描述
地上有一个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
版权声明：本文为博主原创文章，转载请附上博文链接！