剑指Offer——机器人的运动范围

题目描述

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

示例
输入
5,10,10
返回值
21

题解

DFS/BFS。

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][]map=new boolean[rows][cols];
        DFS(map,threshold,0,0);
        int count=0;
        for(int row=0;row<rows;++row){
            for(int col=0;col<cols;++col){
                if(map[row][col]){
                    ++count;
                }
            }
        }
        return count;
    }
    void DFS(boolean[][]map,int threshold,int row,int col){
        // 边界
        if(row>=map.length||row<0||col>=map[0].length||col<0){
            return;
        }
        // 已经确定能走
        if(map[row][col]){
            return;
        }
        // 判断是否能走
        if(sumOfNumber(row)+sumOfNumber(col)<=threshold){
            map[row][col]=true;// 能走
            // 往四个方向扩
            DFS(map,threshold,row-1,col);
            DFS(map,threshold,row+1,col);
            DFS(map,threshold,row,col-1);
            DFS(map,threshold,row,col+1);
        }
    }
    private int sumOfNumber(int a){
        int sum=0;
        while(a!=0){
            sum+=a%10;
            a/=10;
        }
        return sum;
    }
}