剑指Offer（六十六）机器人的运动范围（Java版）

　　描述
　　地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
　　数据范围： 0 le threshold le 15   threshold  15 ，1 le rows,cols le 100 1  rows , cols  100进阶：空间复杂度 O(nm)  O ( nm ) ，时间复杂度 O(nm)  O ( nm ) 示例1
　　输入：1,2,3
　　返回值：3  示例2
　　输入：0,1,3
　　返回值：1  示例3
　　输入：10,1,100
　　返回值：29
　　说明：
　　[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的  示例4
　　输入：5,10,10
　　返回值：21  第一种解法
　　使用dfs（深度优先搜索）来解决，需要注意的一点。得防止重复的点二次计数。代码如下int[][] arr = null; int count = 0; public int firstMovingCount(int threshold, int rows, int cols) {     if(rows < 1 && cols < 1){         return count;     }     if(threshold < 0){         return count;     }     arr = new int[rows][cols];     dsf(threshold,rows,cols,0,0);     return count; }  public void dsf(int threshold, int rows, int cols,int row,int col){     if(row < 0 || row >= rows || col < 0 || col >= cols || arr[row][col] == 1){         return;     }     if(check(row) + check(col) > threshold){         return;     }     arr[row][col] = 1;     count++;     dsf(threshold,rows,cols,row+1,col);     dsf(threshold,rows,cols,row-1,col);     dsf(threshold,rows,cols,row,col+1);     dsf(threshold,rows,cols,row,col-1); }  int check(int num){     int sum = 0;     while (num > 0){         sum += (num % 10);         num = num /10;     }     return sum; }第二种解法
　　使用bfs(广度优先搜索)来解决。对于bfs的特性，采用队列来实现是最好的，因为队列是先进先出，离他最近的访问完之后加入到队列中，最先入队的也是最先出队的，代码如下int[][] arr = null; int count = 0;  int check(int num){     int sum = 0;     while (num > 0){         sum += (num % 10);         num = num /10;     }     return sum; }   public int secondMovingCount(int threshold, int rows, int cols) {     if(rows < 1 && cols < 1){         return count;     }     if(threshold < 0){         return count;     }     arr = new int[rows][cols];     Queue queue = new LinkedList<>();     queue.add(new int[]{0,0});     while (!queue.isEmpty()){         int[] poll = queue.poll();         int i = poll[0];         int j = poll[1];         if(i >= rows || j >= cols || arr[i][j] == 1 || (check(i) + check(j) > threshold)){             continue;         }         arr[i][j] = 1;         count++;         queue.add(new int[]{i+1,j});         queue.add(new int[]{i,j+1});     }     return count; }