宽度优先遍历 BFS

宽度优先遍历 BFS

1· 机器人的运动范围 (13 剑指offer )

• 这道题 可以使用DFS 或 BFS 来求解， 但是DFS 可能会导致栈溢出， 所以这里选择BFS算法 + queue 的数据结构
• 解题思路： 从左上角开始，BFS 遍历合法扩展没有遍历过的格子，最后所有遍历过的个数 就是合法的答案， 所以时间复杂度O（mn）所有格子的个数， 在C++ 中pointer 一秒可以遍历 1亿个 格子。
• 这道题里的BFS 是 由queue 数据结构 来存储 坐标， 因为java 中不能直接 存放pair， 所以存放在 queue 里的 元素可以是数组。

public int movingCount(int threshold , int rows , int cols ){  
   if(rows <=0 || cols <= 0)
     return 0;
    int res = 0; 
   boolean [][] visited = new boolean [rows][cols];
   Queue<int[]> queue = new LinkedList<>();
   int[] dx = {-1, 0, 1, 0},  dy = {0, 1, 0, -1}; 
   queue.offer(new int[] {0,0});
   while( !queue.isEmpty()){
       int[] arr = queue.poll();
       if( get_sum_Digit(arr[0]) + get_sum_Digit(arr[1]) > threshold || arr[0] >= rows
           || arr[1] >= cols || arr[0] < 0 || arr[1] < 0 || visited[arr[0]][arr[1]] ) continue;
       res ++; 
       visited[arr[0]][arr[1]] = true; 
       for(int i=0; i<4; i++) {
           queue.offer(new int[]{ arr[0] + dx[i] , arr[1] +  dy[i]}); 
       }           
   }  /* while */
   return  res;
}

public int get_sum_Digit(int input) {
   int sum = 0;
   while(input != 0) {
     sum += input %10;
     input /= 10;
   }
 return  sum;
}