本文共 1583 字，大约阅读时间需要 5 分钟。

DFS利用递归栈实现，BFS使用队列实现。BFS可以套模板，这里需要自己实现的就是求数位之和函数，利用整除和取余运算操作。

• 其中这里有个优化点：向右向下走就可以了，不用向上和向左也可以遍历所有坐标。
• 关于矩阵搜索的经典方向数组要掌握
• 将题目中的位数之和k看做和超出边界或已访问过的元素一样的障碍物，遇到了 continue 跳过继续搜索。

class Solution {
       public int movingCount(int m, int n, int k) {
           if(k == 0){
               return 1;        }        Queue
   
     queue = new LinkedList<>();        // direction arr        int[] xDirection = {
   0,1};        int[] yDirection = {
   1,0};        // 存储已访问过的元素数组        boolean[][] visited = new boolean[m][n];        queue.offer(new int[]{
   0,0});        visited[0][0] = true;        int ans = 1;        while(!queue.isEmpty()){
               int[] cell = queue.poll();            // 坐标的x值和y值            int x = cell[0],y = cell[1];            // 利用方向数组，生成向右和向下的新坐标;x,y只能每次只能其中一个 +1            for(int i=0;i<2;i++){
                   int xNew = xDirection[i] + x;                int yNew= yDirection[i] + y;                // 如果x，y超出矩阵界限，或者坐标的数位之和大于k就跳过，又或者该元素已经访问过                if(xNew < 0 || xNew >= m || yNew < 0 || yNew >= n || visited[xNew][yNew] || get(xNew) + get(yNew) > k){
                       continue;                }                // 将符合条件的新坐标入队，继续搜索;同时在已访问数组中标记                queue.offer(new int[]{
   xNew,yNew});                visited[xNew][yNew] = true;                // 能达到的格子数加1                ans++;            }        }        return ans;    }    // get() 计算数位之和,利用 / 和 %    private int get(int x){
           int res = 0;        while(x!=0){
               // 个位数            res += x % 10;            x /= 10;        }        return res;    }}
   

转载地址：http://kpozi.baihongyu.com/