机器人的运动范围

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

• DFS

• Java 代码：

public class Solution {
    public int res = 0;
    public int[][] position = new int[][]{{-1,0}, {1,0}, {0,-1},{0,1}};
    public int movingCount(int threshold, int rows, int cols)
    {
        boolean[][] visited = new boolean[rows][cols];
        dfs(0,0, rows, cols, visited, threshold);
        return res;
    }
    
    private void dfs(int row, int col, int rows, int cols, boolean[][] visited, int threshold) {
        if(row < 0 || col < 0 || row >= rows || col >= cols || visited[row][col] || countSum(row, col, threshold)) {
            return;
        }
        res++;
        visited[row][col] = true;
        for(int[] pos : position) {
            dfs(row + pos[0], col + pos[1], rows, cols, visited, threshold);
        }    
    }
    
    private boolean countSum(int row, int col, int threshold) {
        int res = 0;
        while(row != 0) {
            res += row % 10;
            row = row / 10;
        }
        while(col != 0) {
            res += col % 10;
            col /= 10;
        }
        return res > threshold;
    }
}

• C++ 代码

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        int count = 0;
        bool *visited = new bool[rows*cols];
        memset(visited, 0 , rows*cols);
        count = dfs(threshold, rows, cols, 0, 0,  visited);
        delete[] visited;
        return count;
    }
    int dfs(int threshold, int rows, int cols,int i, int j, bool *visited){
        if(i<0||j<0||i>=rows||j>=cols||!isEnter(threshold,i,j)) return 0;
        if(!visited[i*cols+j]){
            visited[i*cols+j] = true;
            return 1+dfs(threshold, rows, cols, i-1, j,  visited) + dfs(threshold, rows, cols, i+1, j,  visited)
                    +dfs(threshold, rows, cols, i, j-1,  visited) + dfs(threshold, rows, cols, i, j+1,  visited);
        }
        return 0;
    }
    bool isEnter(int threshold,int i, int j){
        int sum = 0;
        while(i){
            sum += i%10;
            i = i/10;
        }
        while(j){
            sum += j%10;
            j = j/10;
        }
        if(sum>threshold) return false;
        return true;
    }
};