机器人的运动范围：DFS

Problem: 剑指 Offer 13. 机器人的运动范围

思路

首先定义好地图，上下左右四个方向也就是{{1,0},{0,1},{-1,0},{0,-1}}，然后我们另外定义一个方法来判断题目要求的下标位数和是否大于k，

  boolean check(int x,int y,int k){int s = 0;while(x!=0){s+=x%10;x = x/10;}while(y!=0){s+=y%10;y = y/10;}return s>k;}

然后定义dfs遍历，要额外传入一个vst[][]辨别是否已经走过，防止无限循环造成栈溢出，外面定义res一开始是1因为最开始的{0，0}格子一定会占一个结果，然后每遍历一遍+1即可

解题方法

描述你的解题方法

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(n)$

• 空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution {public int movingCount(int m, int n, int k) {this.m = m;this.n = n;return dfs(0,0,k,new boolean[m][n]);}int[][] dirs = {{1,0},{0,1},{-1,0},{0,-1}};int m,n;int res = 1;int dfs(int x,int y,int k,boolean[][] vst){vst[x][y] = true;for(int[] dir :dirs){int nx = x + dir[0];int ny = y + dir[1];if(nx<0 || ny<0 || nx>=m || ny >= n || check(nx,ny,k) || vst[nx][ny]){continue;}res = dfs(nx,ny,k,vst)+1;}return res;}boolean check(int x,int y,int k){int s = 0;while(x!=0){s+=x%10;x = x/10;}while(y!=0){s+=y%10;y = y/10;}return s>k;}
}