018 机器人的运动范围

  1 package first;
  2 
  3 public class RobotMove {
  4     public int movingCount(int threshold, int rows, int cols) {
  5         if (rows <= 0 || cols <= 0 || threshold < 0)
  6             return 0;
  7 
  8         boolean[] isVisited = new boolean[rows * cols];
  9         int count = movingCountCore(threshold, rows, cols, 0, 0, isVisited);// 用两种方法试一下
 10         return count;
 11     }
 12 
 13     private int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] isVisited) {
 14         if (row < 0 || col < 0 || row >= rows || col >= cols || isVisited[row * cols + col] || cal(row) + cal(col) > threshold)
 15             return 0;
 16         isVisited[row * cols + col] = true;
 17         return 1 + movingCountCore(threshold, rows, cols, row - 1, col, isVisited)
 18                 + movingCountCore(threshold, rows, cols, row + 1, col, isVisited)
 19                 + movingCountCore(threshold, rows, cols, row, col - 1, isVisited)
 20                 + movingCountCore(threshold, rows, cols, row, col + 1, isVisited);
 21     }
 22 
 23     private int cal(int num) {
 24         int sum = 0;
 25         while (num > 0) {
 26             sum += num % 10;
 27             num /= 10;
 28         }
 29         return sum;
 30     }
 31 
 32     // ========测试代码=========
 33     void test(String testName, int threshold, int rows, int cols, int expected) {
 34         if (testName != null)
 35             System.out.print(testName + ":");
 36 
 37         if (movingCount(threshold, rows, cols) == expected)
 38             System.out.println("Passed.");
 39         else
 40             System.out.println("Failed.");
 41     }
 42 
 43     // 方格多行多列
 44     void test1() {
 45         test("Test1", 5, 10, 10, 21);
 46     }
 47 
 48     // 方格多行多列
 49     void test2() {
 50         test("Test2", 15, 20, 20, 359);
 51     }
 52 
 53     // 方格只有一行，机器人只能到达部分方格
 54     void test3() {
 55         test("Test3", 10, 1, 100, 29);
 56     }
 57 
 58     // 方格只有一行，机器人能到达所有方格
 59     void test4() {
 60         test("Test4", 10, 1, 10, 10);
 61     }
 62 
 63     // 方格只有一列，机器人只能到达部分方格
 64     void test5() {
 65         test("Test5", 15, 100, 1, 79);
 66     }
 67 
 68     // 方格只有一列，机器人能到达所有方格
 69     void test6() {
 70         test("Test6", 15, 10, 1, 10);
 71     }
 72 
 73     // 方格只有一行一列
 74     void test7() {
 75         test("Test7", 15, 1, 1, 1);
 76     }
 77 
 78     // 方格只有一行一列
 79     void test8() {
 80         test("Test8", 0, 1, 1, 1);
 81     }
 82 
 83     // 机器人不能进入任意一个方格
 84     void test9() {
 85         test("Test9", -10, 10, 10, 0);
 86     }
 87 
 88     public static void main(String[] args) {
 89         RobotMove demo = new RobotMove();
 90         demo.test1();
 91         demo.test2();
 92         demo.test3();
 93         demo.test4();
 94         demo.test5();
 95         demo.test6();
 96         demo.test7();
 97         demo.test8();
 98         demo.test9();
 99     }
100 }