本文共 2710 字，大约阅读时间需要 9 分钟。

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

示例 1：

输入：m = 2, n = 3, k = 1

输入：m = 3, n = 1, k = 0

来源：力扣（LeetCode）

广度优先遍历

//广度优先遍历BFSpublic class Work2 {
       public int movingCount(int m, int n, int k) {
           boolean[][] isUsed = new boolean[m][n]; //走过的格子为true        Queue
   
     queue = new LinkedList<>();//队列来放格子的x和y下标        queue.offer(new int[]{
   0,0});    //给队列放最左上角的格子        isUsed[0][0] = true;    //左上角格子置为走过的格子        int count = 1;  //用来计数可以走的格子数        int[] addx = {
   0, 1};    //用来向右移动        int[] addy = {
   1, 0};    //用来向下移动        //出循环条件：队列为空        while(!queue.isEmpty()) {
               int[] arr = queue.poll();   //出队并记录此格子位置            //依次遍历此格子的右格子和下格子            //i==0 遍历右格子            //i==1 遍历下格子            for(int i = 0; i < 2; i++) {
                   int x = arr[0] + addx[i];   //让x下标走动                int y = arr[1] + addy[i];   //让y下标走动                //如果走后的格子为以下条件，则这个格子不能走到，自然不能入队                //1.该位置越界                //2.该位置超过k条件                //3.该位置已经走过了                if(x < 0 || x > m-1 || y < 0 || y > n-1 || sum(x)+sum(y) > k || isUsed[x][y]) {
                       continue;                }                //程序能走到这里，证明此位置可以走到，则让此位置入队                queue.offer(new int[]{
   x,y});    //入队此格子                isUsed[x][y] = true;    //此格子置为走过的格子                count++;    //可以走的格子数加一            }        }        //程序走到这，说明队列里已经没有了可以遍历的格子，最后返回可以走的格子数        return count;    }    //返回该数所有位的和 例如123 返回1+2+3=6    public int sum(int a) {
           int count = 0;        while(a != 0) {
               count = count + a%10;            a = a/10;        }        return count;    }}
   

深度优先遍历

//深度优先遍历DFSpublic class Work1 {
       public int movingCount(int m, int n, int k) {
           boolean[][] isUsed = new boolean[m][n];        return dfs(0, 0, m, n, k, isUsed);    }    public int dfs(int i, int j, int m, int n, int k, boolean[][] isUsed) {
           if(i < 0 || i > m-1 || j < 0 || j > n-1 || sum(i)+sum(j) > k || isUsed[i][j]) {
               return 0;        }        isUsed[i][j] = true;        int result = dfs(i-1, j, m, n, k, isUsed) +                dfs(i+1, j, m, n, k, isUsed) +                dfs(i, j-1, m, n, k, isUsed) +                dfs(i, j+1, m, n, k, isUsed) + 1;        return result;    }    public int sum(int a) {
           int count = 0;        while(a != 0) {
               count = count + a%10;            a = a/10;        }        return count;    }}

转载地址：http://jkxb.baihongyu.com/