难度**

**中等

思路

BFS + 剪枝

  • 这题与数组匹配字符串相似，可以使用 BFS 算法解决问题。

    1. public class NO13_The_range_of_motion_of_the_robot {
    2.   public static void main(String[] args) {
    3.       System.out.println(movingCount_1(3, 2, 17));
    4.   }
    6.   static int total = 0;
    8.   public static int movingCount_1(int m, int n, int k) {
    9.       if (k == 0)
    10.           return 1;
    11.       boolean[][] array = new boolean[m][n];
    12.       doRecursion(0, 0, k, array);
    13.       return total;
    14.   }
    16.   private static boolean doRecursion(int i, int j, int k, boolean[][] array) {
    17.       if (i < 0 || i > array.length - 1 || j < 0 || j > array[0].length - 1 || array[i][j])
    18.           return false;
    20.       int sum = i / 10 + i % 10 + j / 10 + j % 10;
    21.       if (sum > k)
    22.           return false;
    24.       // 记录
    25.       array[i][j] = true;
    26.       boolean ret = doRecursion(i - 1, j, k, array)
    27.               || doRecursion(i + 1, j, k, array)
    28.               || doRecursion(i, j - 1, k, array)
    29.               || doRecursion(i, j + 1, k, array);
    30.       total++;
    31.       return ret;
    32.   }
    33. }

    | 时间复杂度 | O(n) | | —- | —- | | 空间复杂度 | O(mn) |


  • | 时间复杂度 | O(n) | | —- | —- | | 空间复杂度 | O(1) |

总结