题解 | #机器人的运动范围#

机器人的运动范围：基本思路是广度优先遍历。在遍历一个点之前，先对其进行边界检查和门限检查。设置一个二维数组，用于表示该点是否已经被走过，如果被走过，则不参与计数。判断门限时，这里使用了字符串的形式，也可以采用其它形式。时间复杂度：O（mn)空间复杂度O(mn)

public class Solution {
    int count = 0;
    class Pos{
        int px;
        int py;
        public Pos(int px,int py){this.px = px;this.py=py;}
        
    }
    public int movingCount(int threshold, int rows, int cols) {
        int [][] mat =new int[rows][cols];
        Queue<Pos> que = new LinkedList<>();
        que.offer(new Pos(0,0));
        while(!que.isEmpty()){
            Pos p = que.poll();
            if(p.px<rows&&p.px>=0&&p.py<cols&&p.py>=0){
                if(bitSum(p.px+""+p.py)<=threshold&&mat[p.px][p.py]==0){
                    mat[p.px][p.py]=1;
                    count++;
                    que.offer(new Pos(p.px-1,p.py));
                    que.offer(new Pos(p.px,p.py-1));
                    que.offer(new Pos(p.px+1,p.py));
                    que.offer(new Pos(p.px,p.py+1));
                }
            }
        }
        return count;
    }
    public int bitSum(String s){
        int sum = 0;
        for(int i=0;i<s.length();++i){
            sum+=s.charAt(i)-'0';
        }
        return sum;
    }
}