地上有一个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
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100 0 <= k <= 20
思路：
dfs每次遍历四个方向，没有越界且行列数字之和小于等于k则递归遍历它，否则跳过
1 class Solution { 2 3 // 获取数字的数位之和 4 public int getSumOfBit(int a){ 5 int sum = 0; 6 while(a != 0){ 7 sum += a % 10; 8 a /= 10; 9 } 10 return sum; 11 } 12 13 public boolean[][] vis; // 判断是否遍历过 14 public int m, n, k; // 记录m,n,k，减少变量传递的开销 15 public int cnt = 0; // 计数器，记录能到达的格子数量 16 17 public int movingCount(int m, int n, int k) { 18 19 vis = new boolean[m][n]; 20 this.m = m; 21 this.n = n; 22 this.k = k; 23 24 // dfs遍历 25 dfs(0, 0); 26 27 return cnt; 28 } 29 30 public int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 31 32 public void dfs(int row, int col){ 33 vis[row][col] = true; 34 cnt++; 35 // 每次遍历四个方向，没有越界且行列数字之和小于等于k则递归遍历它，否则跳过 36 for(int i = 0; i < 4; i++){ 37 int newRow = row + dir[i][0]; 38 int newCol = col + dir[i][1]; 39 if(newRow <m && newRow >= 0 && newCol < n && newCol >= 0 40 && (getSumOfBit(newRow) + getSumOfBit(newCol)) <= k && vis[newRow][newCol] == false){ 41 dfs(newRow, newCol); 42 } 43 } 44 } 45 }
leetcode运行时间为2ms, 空间为35.4MB
复杂度分析：
时间复杂度：每个单元格最多被遍历一次，最坏情况下遍历所有单元格，所以时间复杂度为O(n*m)
空间复杂度：需要一个大小为n*m的 vis[][]数组记录单元格是否被访问过，递归也会有一个递归栈的复杂度，最大深度为max(m, n), 所以空间复杂度为O(n*m + max(m,n))， 之所以可以把max(m, n)这个线性复杂度省略是因为，这个递归栈的复杂度，递归栈的每层的复杂度不能简单和一个数组的一个单元空间相提并论。
改进版：dfs, 但是只遍历两个方向
仔细想想，因为我们探测起点是左上角的点， 所以其实每次探测只需要探测两个方向，向右和向下，就能找到所有可达的单元格，所以可以对算法的复杂度达到一个稍加改进的效果
1 class Solution { 2 3 // 获取数字的数位之和 4 public int getSumOfBit(int a){ 5 int sum = 0; 6 while(a != 0){ 7 sum += a % 10; 8 a /= 10; 9 } 10 return sum; 11 } 12 13 public boolean[][] vis; // 判断是否遍历过 14 public int m, n, k; // 记录m,n,k，减少变量传递的开销 15 public int cnt = 0; // 计数器，记录能到达的格子数量 16 17 public int movingCount(int m, int n, int k) { 18 19 vis = new boolean[m][n]; 20 this.m = m; 21 this.n = n; 22 this.k = k; 23 24 // dfs遍历 25 dfs(0, 0); 26 27 return cnt; 28 } 29 30 public int[][] dir = {{1, 0}, {0, 1}}; 31 32 public void dfs(int row, int col){ 33 vis[row][col] = true; 34 cnt++; 35 // 每次遍历下和右两个方向，没有越界且行列数字之和小于等于k则递归遍历它，否则跳过 36 for(int i = 0; i < 2; i++){ 37 int newRow = row + dir[i][0]; 38 int newCol = col + dir[i][1]; 39 if(newRow <m && newRow >= 0 && newCol < n && newCol >= 0 40 && (getSumOfBit(newRow) + getSumOfBit(newCol)) <= k && vis[newRow][newCol] == false){ 41 dfs(newRow, newCol); 42 } 43 } 44 } 45 }
稍微调整一个dfs()函数的结构，使程序更简洁一些
1 class Solution { 2 3 // 获取数字的数位之和 4 public int getSumOfBit(int a){ 5 int sum = 0; 6 while(a != 0){ 7 sum += a % 10; 8 a /= 10; 9 } 10 return sum; 11 } 12 13 public boolean[][] vis; // 判断是否遍历过 14 // public int cnt = 0; 15 16 public int movingCount(int m, int n, int k) { 17 18 vis = new boolean[m][n]; 19 // dfs遍历 20 int cnt = dfs(m, n, k, 0, 0); // 计数器，记录能到达的格子数量 21 return cnt; 22 } 23 24 public int dfs(int m, int n, int k, int row, int col){ 25 if(row >= m || col >= n || vis[row][col] || getSumOfBit(row) + getSumOfBit(col) > k){ 26 return 0; 27 } 28 vis[row][col] = true; 29 // 每次遍历下和右两个方向，没有越界且行列数字之和小于等于k则递归遍历它，否则跳过 30 return 1 + dfs(m, n, k, row + 1, col) + dfs(m, n, k, row, col + 1); 31 } 32 }
leetcode 执行用时：1 ms > 85.23%, 内存消耗：35.2 MB > 97.58%
复杂度分析：
时间复杂度：O(m*n)。同样是遍历了所有可达的单元格，所以时间复杂度为O(m*n)
空间复杂度：O(m*n) + max(m, n)。取决于递归栈的深度，深度最大为max(m, n), 另外还需要一个vis[][]的二维数组，空间花费为O(n*m), 所以总的空间复杂度为O(n*m + max(m, n)).