个人想法，有错误请批！

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路

这道题我先是用BFS(广搜)的思路去解决的，BFS一般是用来查找源点到目的结点之间的最短路径，它的实现思路是通过一个点往外扩散，然后外层点再往外扩散，一直持续下去，直到碰到目的结点，那么扩散的层次一定是最小的，可以幻想成一颗石头丢进水里，水的波纹不停往外扩，而这道题可以利用bfs扩散的特点，不停往外扩散，记录扩散走过的格子数，直到不能扩为止，答案就over了。
至于DFS（深搜）的思路，也是可以解决的，就是一路走到黑，走到死胡同再退回一步，从另一个方向一路走到黑，重复以上过程，直到全部可走方格都走完为止。可以递归、可以非递归（用栈实现）

代码实现

递归版本实现DFS

/**
     * 递归版本实现dfs
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public int movingCount2(int threshold, int rows, int cols) {
        if (threshold < 0 || rows <= 0 || cols <= 0)
            return 0;
        boolean[][] visited = new boolean[rows][cols];
        return dfs(threshold, 0, 0, rows, cols, visited);
    }

    private int dfs(int threshold, int x, int y, int rows, int cols, boolean[][] visited) {
        //先判断当前结点是否可以走
        if(judge(x,y, visited, rows,cols, threshold)){
            visited[x][y] = true;
            //获取从(x,y)四个方位出发，可以走的路径长度
            return 1 + dfs(threshold, x -1, y, rows, cols, visited) + //上
                    dfs(threshold, x , y + 1, rows, cols, visited) + //右
                    dfs(threshold, x +1, y, rows, cols, visited) +//下
                    dfs(threshold, x , y - 1, rows, cols, visited);//左
        }else {
            //以当前结点不能进行扩散，则路径长度为0
            return 0;
        }
    }
/**
     * 判断(x,y)方块是否可以走
     *
     * @param x
     * @param y
     * @param visited
     * @param rows
     * @param cols
     * @return
     */
    private boolean judge(int x, int y, boolean[][] visited, int rows, int cols, int threshold) {
        //getSum(x, y) > threshold判断位数和是否符合条件
        if (x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] == true || getSum(x, y) > threshold)
            return false;
        else
            return true;
    }

    private int getSum(int x, int y) {
        //获取x，y坐标的位数和
        int sum = 0;
        while (x % 10 != 0) {
            sum += x % 10;
            x = x / 10;
        }
        while (y % 10 != 0) {
            sum += y % 10;
            y = y / 10;
        }
        return sum;
    }

BFS版本，使用队列保存走过的点

    public int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows <= 0 || cols <= 0)
            return 0;
        boolean[][] visited = new boolean[rows][cols];
        ArrayList<Integer> paths = new ArrayList<>();
        int count = 0;
        //将(0,0)结点进队
        paths.add(0);
        count++;
        visited[0][0] = true;
        while (paths.size() > 0) {
            //取出队首
            int heap = paths.remove(0);
            //找出上下左右四个可以走过的方块
            //heap一维坐标先转成二维坐标
            int x = heap / cols;
            int y = heap % cols;
            int x1 = 0, y1 = 0;//下一个方块的坐标
            int dict = 0;
            while (dict <= 3) {
                switch (dict) {
                    case 0:
                        x1 = x - 1;
                        y1 = y;
                        break;
                    case 1:
                        x1 = x;
                        y1 = y + 1;
                        break;
                    case 2:
                        x1 = x + 1;
                        y1 = y;
                        break;
                    case 3:
                        x1 = x;
                        y1 = y - 1;
                        break;
                }
                if (judge(x1, y1, visited, rows, cols, threshold)) {
                    //当前方块可以走，进队
                    count++;
                    visited[x1][y1] = true;
                    paths.add(x1 * cols + y1);
                }
                dict++;
            }
        }
        return count;
    }

    /**
     * 判断(x,y)方块是否可以走
     *
     * @param x
     * @param y
     * @param visited
     * @param rows
     * @param cols
     * @return
     */
    private boolean judge(int x, int y, boolean[][] visited, int rows, int cols, int threshold) {
        //getSum(x, y) > threshold判断位数和是否符合条件
        if (x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] == true || getSum(x, y) > threshold)
            return false;
        else
            return true;
    }

    private int getSum(int x, int y) {
        //获取x，y坐标的位数和
        int sum = 0;
        while (x % 10 != 0) {
            sum += x % 10;
            x = x / 10;
        }
        while (y % 10 != 0) {
            sum += y % 10;
            y = y / 10;
        }
        return sum;
    }