12_机器人的运动范围

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

分析：倘若我们把矩阵的每一个“格子”抽象成一个“结点”，把“格子相邻”抽象为“结点连通”（结点之间存在无向边），把“无法进入的格子”抽象成“与所有普通结点都不连通（不存在无向边）的孤点”，则整个问题可以抽象为：从某个结点出发，寻找无向图的连通分量的节点个数。很显然，可以使用DFS或者BFS进行实现。

思路：使用深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

    // 函数getDigitSum用来得到一个数的数位之和,如number=35，返回3+5=8
    public int getDigitSum(int number){
        int sum = 0;
        while(number>0){
            sum+=number%10; // ，若为十位数，取出十位
            number/=10;  // 取出个位
        }
        return sum;
    }
    // 判断是否能进入坐标为（row, col)的方格
    public boolean check(int threshold, int rows, int cols, int row, int col, boolean[] visited){
        if(row>=0&&row<rows&&col>=0&&col<cols
                &&getDigitSum(row)+getDigitSum(col)<=threshold
                &&!visited[row*cols+col]){
            // 此处，行坐标和列坐标的数位之和小于于k的格子，没有访问过的返回true
            return true;
        }
        return false;
    }
    // 进行dfs,设置辅助函数visited
    public int movingCount(int threshold, int rows, int cols){
        if(threshold<0||rows<=0||cols<=0){  // 判断边界
            return 0;
        }
        // 设置辅助函数visited，空间大小为方格的总数
        boolean[] visited = new boolean[rows*cols];
        int count = movingCountCore(threshold,rows,cols,0,0,visited);
        return count;
    }

    public int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] visited){
        int count = 0;
        if(check(threshold,rows,cols,row,col,visited)){
            visited[row*cols+col] = true;  // 把当前的位置设定为已经访问
            // 对每个方向都进行试探
            count = 1+movingCountCore(threshold, rows, cols, row-1, col, visited)+
                    movingCountCore(threshold, rows, cols, row, col-1, visited)+
                    movingCountCore(threshold, rows, cols, row+1, col, visited)+
                    movingCountCore(threshold, rows, cols, row, col+1, visited);
        }
        return count;
    }