【剑指offer】24. 机器人的运动范围（java选手）

题目链接

题目链接

题目描述

地上有一个 m 行和 n列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

注意:
0<=m<=50
0<=n<=50
0<=k<=100

样例1 输入：k=7, m=4, n=5 输出：20

样例2 输入：k=18, m=40, n=40 输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

题目考察知识点

图论！
深搜or光搜
当前节点可以达到的节点为上下左右四个方向

解题代码

深搜dfs

递归实现

class Solution {// 深度优先// 在确定完是否满足条件后，[先加结果，然后标为已走]，然后再进行dfsint result;// 可以走的方向int dir[][] = {{-1,0},{1,0},{0,1},{0,-1}};public int movingCount(int threshold, int rows, int cols){// 判断临界情况，也就是rows和cols都为0if(rows == 0 || cols == 0){return 0;}// 判断是否走过boolean[][] used = new boolean[rows][cols];result = 0;// 判断0,0是否符合条件if(!judge(0,0,threshold))   return 0;result ++;used[0][0] = true;dfs(0, 0, rows, cols, threshold, used);return result;}// 深度优先public void dfs(int inow, int jnow, int rows, int cols, int threshold, boolean[][] used){for(int i = 0; i < 4; i ++){int inext = inow + dir[i][0];int jnext = jnow + dir[i][1];if(inext >= 0 && inext < rows && jnext >=0 && jnext < cols){// 满足条件，才进行下一个dfsif(used[inext][jnext]==false && judge(inext, jnext, threshold)){result ++;used[inext][jnext] = true;dfs(inext, jnext, rows, cols, threshold, used);}}}}// 是否满足条件public boolean judge(int i, int j, int threshold){int now = 0;while(i != 0){now += i % 10;i = i / 10;}while(j != 0){now += j % 10;j = j / 10;}// 不满足if(now > threshold){return false;}else{return true;}}
}

注意注意！！！

• used数组是必须要有的！标识一下当前哪些格子被判断过了
• 判断临界条件
  • 特别是！哪个rows和cols都为0的情况
• 判断完是否符合条件再去进行dfs更容易

广搜bfs

队列实现
队列不为空的时候一直循环
符合条件的进入队列

class Solution {// 广度优先// 在确定完是否满足条件后，[先加结果，然后标为已走]，然后再进队列int result;// 可以走的方向int dir[][] = {{-1,0},{1,0},{0,1},{0,-1}};public int movingCount(int threshold, int rows, int cols){// 判断临界情况，也就是rows和cols都为0if(rows == 0 || cols == 0){return 0;}// 判断是否走过boolean[][] used = new boolean[rows][cols];result = 0;bfs(rows, cols, threshold, used);return result;}// 广度优先public void bfs(int rows, int cols, int threshold, boolean[][] used){Deque<int[]> deque = new LinkedList<>();if(judge(0, 0, threshold)){deque.push(new int[]{0, 0});used[0][0] = true;result ++;}while(!deque.isEmpty()){int[] now = deque.pop();int inow = now[0];int jnow = now[1];for(int i = 0; i < 4; i ++){int inext = inow + dir[i][0];int jnext = jnow + dir[i][1];if(inext >= 0 && inext < rows && jnext >=0 && jnext < cols){// 满足条件，才进入队列if(used[inext][jnext]==false && judge(inext, jnext, threshold)){result ++;used[inext][jnext] = true;deque.push(new int[]{inext, jnext});}}}}return;}// 是否满足条件public boolean judge(int i, int j, int threshold){int now = 0;while(i != 0){now += i % 10;i = i / 10;}while(j != 0){now += j % 10;j = j / 10;}// 不满足if(now > threshold){return false;}else{return true;}}
}