机器人的运动范围

题目

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

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：

1 <= n,m <= 100
0 <= k <= 20

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

简单的思路就是广度优先搜索遍历.

再优化的话也可以使用递推,同时用数组来存储已遍历过得位置

代码

BFS

class Solution {
    public int movingCount(int m, int n, int k) {
        Queue<Point> queue = new LinkedList();
        Set<Point> set = new HashSet();
        queue.offer(new Point(0,0));
        int result = 0;
        while(!queue.isEmpty()){
            Point point = queue.poll();
            int x = point.x;
            int y = point.y;
            if(x >= 0 && x < n && y >= 0 && y < m && check(x,y,k)){
                if(y+1 < m){
                    Point down = new Point(x,y+1);
                    if(!set.contains(down)){
                        queue.offer(down);
                        set.add(down);
                    }
                }
                if(x +1 < n){
                    Point right = new Point(x+1,y);
                    if(!set.contains(right)){
                        queue.offer(right);
                        set.add(right);
                    }
                }
                result++;
            }
        }
        return result;
    }

    public boolean check(int x,int y,int k){
        int sum = x / 100 + x / 10 + x % 10 + y /100 + y/10 + y%10;
        return sum <= k;
    }
}

class Point{
    int x;
    int y;
    public Point(int x,int y){
        this.x = x;
        this.y = y;
    }
     @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x &&
                y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

优化后的代码

class Solution {
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        visited=new boolean[m][n];
        return DFS(0,0,k);
    }
    
    
    public int DFS(int m,int n,int k){
        if(m<0||n<0||m>=visited.length||n>=visited[0].length||getNum(m,n)>k||visited[m][n])
        {
            return 0;
        }
        visited[m][n]=true;
        return 1+DFS(m-1,n,k)+DFS(m+1,n,k)+DFS(m,n-1,k)+DFS(m,n+1,k);
        
    } 
    
    public int getNum(int m,int n){
        return m/100+m/10+m%10+n/100+n/10+n%10;
    }
}