java版BFS

java 代码

class Solution {
    static boolean flag[][]=null;
    static class Coordinate{
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    /*
     * 获得数字的数位之和
     */
    private  int getDigitSum(int col) {
        int sum=0;
        while(col!=0){
            sum+=col%10;
            col=col/10;
        }
        return sum;
    }
    public  int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<0||rows<0||cols<0)
            return 0;
        if(rows<=0&&cols<=0)
            return 0;
        flag= new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(flag[i],true);
        }
        Coordinate head=new Coordinate(0,0);
        Queue<Coordinate> queue=new LinkedList<>();
        queue.add(head);
        flag[0][0]=false;
        int cnt=1;
        while (!queue.isEmpty()){
            Coordinate tmp=queue.poll();
            int x=tmp.x;
            int y=tmp.y;
            if (getDigitSum(x+1)+getDigitSum(y)<=threshold&&x+1<rows&&flag[x+1][y]){
                queue.add(new Coordinate(x+1,y));
                flag[x+1][y]=false;
                cnt++;
            }
            if (getDigitSum(x-1)+getDigitSum(y)<=threshold&&x-1>=0&&flag[x-1][y]){
                queue.add(new Coordinate(x-1,y));
                flag[x-1][y]=false;
                cnt++;
            }
            if (getDigitSum(y+1)+getDigitSum(x)<=threshold&&y+1<cols&&flag[x][y+1]){
                queue.add(new Coordinate(x,y+1));
                flag[x][y+1]=false;
                cnt++;
            }
            if (getDigitSum(y-1)+getDigitSum(x)<=threshold&&y-1>=0&&flag[x][y-1]){
                flag[x][y-1]=false;
                queue.add(new Coordinate(x,y-1));
                cnt++;
            }
        }
        return cnt;
    }
}