机器人的运动范围

import java.util.*;
public class Solution {
    public int sum = 0;
    public int movingCount(int threshold, int rows, int cols) {
        int[][] a = new int[rows][cols];
        search(threshold, rows, cols, 0, 0, a);
        return sum;
    }
    public void search(int threshold, int rows, int cols, int nowRow, int nowCol,
                       int [][]a) {
        if (nowRow >= rows || nowCol >= cols) {
            return;
        }
        //剪枝判断
        if (a[nowRow][nowCol] == 1) {
            return;
        }
        int rowTen = nowRow / 10;
        int rowSingle = nowRow - 10 * rowTen;
        int colTen = nowCol / 10;
        int colSingle = nowCol - 10 * colTen;
        int nowThreshold = rowTen + rowSingle + colTen + colSingle;
        if (nowThreshold > threshold) {
            return;
        }
        if (a[nowRow][nowCol] == 0) {
            sum = sum + 1;
        }
        a[nowRow][nowCol] = 1;
        search(threshold, rows, cols, nowRow + 1, nowCol, a);
        search(threshold, rows, cols, nowRow, nowCol + 1, a);
    }
}

//一道很经典的递归 类似问题还有岛屿问题
public class Solution {
    public int count = 0;
    public int movingCount(int threshold, int rows, int cols) {
        int[][] nums = new int[rows][cols];
        //state作为状态数组看一下当前这个点有没有判断过
        boolean[][] state = new boolean[rows][cols];
        recursion(threshold,rows,cols,0,0,state);
        return count;
    }

    public void recursion(int threshold,int rows,int cols,int i,int j,boolean[][] state){
        //越界的话就返回
        if(i<0 || i>=rows){
            return;
        }
        if(j<0 || j>=cols){
            return;
        }
        //计算一下行数之和和列数之和 看看这个点是否满足要求，不满足就返回
        int sum = 0;
        int k = i;
        while(k/10!=0){
            sum += k%10;
            k = k/10;
        }
        sum += k;
        int l = j;
        while(l/10!=0){
            sum += l%10;
            l = l/10;
        }
        sum += l;
        if(sum>threshold){
            return;
        }
        //我们选的点必须是没被走过的点，因为如果这个点被走过了，再算一遍就会造成重复计算
        if(!state[i][j]){
            //这个点之前没走过，现在我们来走，并把这个点的状态置为true
            state[i][j] = true;
            //能走到这，说明前面的重重条件都满足了，这是我们要的点
            count++;
            //从这个点开始，上下左右每次可以走1步，递归
            recursion(threshold,rows,cols,i-1,j,state);
            recursion(threshold,rows,cols,i+1,j,state);
            recursion(threshold,rows,cols,i,j-1,state);
            recursion(threshold,rows,cols,i,j+1,state);
        }
    }
}

import java.util.*;
public class Solution {
    int rows, cols, threshold;
    boolean[][] visited;
    public int movingCount(int threshold, int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.threshold = threshold;
        visited = new boolean[rows][cols];
        return dfs(0, 0, 0, 0);
    }
    int dfs(int x, int y, int sx, int sy) {
        if(x>=rows || y>=cols || threshold<sx+sy || visited[x][y]) return 0;
        visited[x][y]=true;
        return 1+dfs(x+1,y,(x+1)%10!=0?sx+1:sx-8, sy)+dfs(x,y+1,sx,(y+1)%10!=0?sy+1:sy-8);
    }
}

    public int movingCount(int threshold, int rows, int cols) {
        // 初始化一个方格
        int[][] rect = new int[rows][cols];
        // 从0 0 开始运动
        backTrack(threshold, rect, 0, 0);
        return res;
    }

    // 记录可以到达的方格数目
    int res = 0;
    void backTrack(int threshold, int[][] rect, int i, int j){
        // 计算出i,j各位之和
        int num = i%10 + i/10%10 + i/100 + j%10 + j/10%10 +j/100;
        // 如果越界 ,i,j各位之和大于threshold, rect[i][j] = 1 (回头走) , rect[i][j] = 2 (第二次到达这个格子 因为已经递归过了所以不需要再递归了属于剪枝的操作) 直接return
        if( !(i >= 0 && i < rect.length) || !(j >= 0 && j < rect[0].length) || threshold < num || rect[i][j] == 1 || rect[i][j] == 2) return;
        // 走过的格子标记为1
        rect[i][j] = 1;
        // 总数加一
        res ++;
        // 上下左右
        backTrack(threshold, rect, i - 1, j);
        backTrack(threshold, rect, i + 1, j);
        backTrack(threshold, rect, i , j - 1);
        backTrack(threshold, rect, i , j + 1);
        // 回溯
        rect[i][j] = 2;
    }

import java.util.*;
public class Solution {
    int count = 0;
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] visited = new boolean[rows][cols];
//         dfs(threshold, rows, cols, 0, 0, visited);
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            int m = tmp[0], n = tmp[1];
            if (m >= rows || n >= cols || visited[m][n] || sum(m) + sum(n) > threshold) continue;
            visited[m][n] = true;
            count++;
            if (m + 1 < rows) q.offer(new int[]{m+1, n});
            if (n + 1< cols) q.offer(new int[]{m, n+1});
        }
        return count;
    }
    public void dfs (int threshold, int rows, int cols, int i, int j, boolean[][] visited) {
        if (i >= rows || j >= cols || visited[i][j] || sum(i) + sum(j) > threshold) return;
        visited[i][j] = true;
        count++;
        dfs(threshold, rows, cols, i+1, j, visited);
        dfs(threshold, rows, cols, i, j+1, visited);
    }

    public int sum(int i) {
        int sum = 0;
        while(i != 0) {
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }
}

public class Solution {
    private int result = 0;
    public int movingCount(int threshold, int rows, int cols) {
        int[][] set = new int[rows][cols];
        dfs(threshold,rows,cols,0,0,set);
        return result;
    }
    private void dfs(int threshold, int rows, int cols,
                            int i,int j, int[][] set){
        if(i<0 || i>=rows || j<0 || j>=cols 
           || !isValid(threshold,i,j) || set[i][j]==1){
            return;
        }
        set[i][j]=1;
        result++;
        dfs(threshold,rows,cols,i-1,j,set);
        dfs(threshold,rows,cols,i+1,j,set);
        dfs(threshold,rows,cols,i,j-1,set);
        dfs(threshold,rows,cols,i,j+1,set);
    }
    
    private boolean isValid(int threshold,int rows,int cols){
        int count = 0;
        while(rows>0){
            count += rows%10;
            rows /= 10;
        }
        while(cols>0){
            count += cols%10;
            cols /= 10;
        }
        return count <= threshold;
    }
}

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        boolean dfs[][]=new boolean[rows][cols];//默认全为false
        return arriveNum(threshold,rows,cols,0,0,dfs);
        
    }
    //x，y为当前所在位置
    //dfs数组用来记录走过的路径
    public int arriveNum(int threshold, int rows, int cols,int x,int y,boolean dfs[][]){
        //循环跳出条件
        if(x<0||y<0||x>=rows||y>=cols||dfs[x][y]==true||addResult(x,y)>threshold)return 0;    
        //当前点符合规定，则对他标记
        dfs[x][y]=true;
        return 1+arriveNum(threshold,rows,cols,x+1,y,dfs)+arriveNum(threshold,rows,cols,x-1,y,dfs)
            +arriveNum(threshold,rows,cols,x,y+1,dfs)+arriveNum(threshold,rows,cols,x,y-1,dfs);
    }
    
    public int addResult(int x,int y){    //计算行列数字和
        int result=0,i,j;
        while(x>0){
            result+=x%10;
            x/=10;
        }
        while(y>0){
            result+=y%10;
            y/=10;
        }
        return result;
    }
}

import java.util.*;
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        if (rows == 0 || cols == 0)
            return 0;
        HashSet<String> set = new HashSet<>();
        return getRes(threshold, rows, cols, 0, 0, set);
    }
    
    public int getRes (int threshold, int rows, int cols, int i, int j, HashSet<String> set) {
        //是否超过合理范围
        if (i >= rows || j >= cols)
            return 0;
        //是否已经被检测过
        if (set.contains(i + ", " + j))
            return 0;
        //已经检测过当前位置
        set.add(i + ", " + j);
        //获取数位之和
        int sum = 0;
        int tmpi = i;
        int tmpj = j;
        int tmp = 0;
        while (tmpi > 0) {
            tmp = tmpi % 10;
            sum += tmp;
            tmpi = tmpi / 10;
        }
        while (tmpj > 0) {
            tmp = tmpj % 10;
            sum += tmp;
            tmpj = tmpj / 10;
        }
        if (sum > threshold)
            return 0;
        //符合条件，则算作一个有效位置，继续往下和右走
        //尽管机器人可以走左上右下，但因其起点为（0，0），
        //且右和下也都是来自左和上，说明之前的点已经走过了，
        //也就没必要再重复走了，所有只走右下即可
        return 1 + getRes(threshold, rows, cols, i+1, j, set) + 
            getRes(threshold, rows, cols, i, j+1, set);
    }
}

import java.util.*;

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        int startR = 0;
        int startC = 0;
        Node begin = new Node(startR, startC);
        Set<Node> visited = new HashSet<>();
        movingCount0(begin, visited, rows, cols, threshold);
        return visited.size();
    }
    
     public void movingCount0(Node begin, Set<Node> visited, int rows, int cols, int threhold) {
        int r = begin.r;
        int c = begin.c;
        //已经访问过，或者是阻挡点就不访问了
        if(visited.contains(begin) || isBlock(rows, cols, r, c, threhold)){
            return;
        }
        visited.add(begin);

        //向上一位
        Node up = new Node(r - 1, c);
        movingCount0(up, visited, rows, cols, threhold);

        //向下一位
        Node down = new Node(r + 1, c);
        movingCount0(down, visited, rows, cols, threhold);

        //向左一位
        Node left = new Node(r, c - 1);
        movingCount0(left, visited, rows, cols, threhold);

        //向右一位
        Node right = new Node(r, c + 1);
        movingCount0(right, visited, rows, cols, threhold);
    }

    public boolean isBlock(int rows, int cols, int r, int c, int threhold) {
        //已经超出边界,肯定是阻挡点
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return true;
        }
        if (calSum(r) + calSum(c) > threhold) {
            return true;
        }
        return false;
    }

    private static int calSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num = num / 10;
        }
        return sum;
    }

    class Node {
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return r == node.r &&
                    c == node.c;
        }

        @Override
        public int hashCode() {
            return Objects.hash(r, c);
        }
    }

}

public class Solution {
    int m;
    int n;
    public int movingCount(int threshold, int rows, int cols) {
        m = rows;
        n = cols;
        boolean[][] can = new boolean[rows][cols];
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                can[i][j] = (bit(i) + bit(j)) <= threshold;
        int ans = 0;
        boolean[][] visited = new boolean[rows][cols];
        dfs(can, visited, 0, 0);
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                if(visited[i][j])
                    ans++;
        return ans;
    }
    
    public void dfs(boolean[][] can, boolean[][] visited, int i, int j){
        if(i < 0 || i >= m || j < 0 || j >= n)
            return;
        if(!can[i][j] || visited[i][j])
            return;
        visited[i][j] = true;
        dfs(can, visited, i + 1, j);
        dfs(can, visited, i - 1, j);
        dfs(can, visited, i, j + 1);
        dfs(can, visited, i, j - 1);
    }
    
    public int bit(int x){
        int ans = 0;
        while(x > 0){
            ans += x % 10;
            x = x / 10;
        }
        return ans;
    }
}

 private int res = 0;
    private  boolean[][] flags  = null;
    public int movingCount(int threshold, int rows, int cols) {
        flags = new boolean[rows][cols];
        Queue<Integer> queueX = new LinkedList<>();
        Queue<Integer> queueY = new LinkedList<>();
        queueX.add(0);
        queueY.add(0);
        res++;
        flags[0][0]=true;
        while(!queueX.isEmpty()){
            int size = queueX.size();
            while(size>0){
                int x = queueX.poll();
                int y = queueY.poll();
                if(x+1<rows&&(!flags[x+1][y])&&!overThreshold(threshold,x+1,y)){
                    res++;
                    flags[x+1][y]=true;
                    queueX.add(x+1);
                    queueY.add(y);
                }
                if(y+1<cols&&(!flags[x][y+1])&&!overThreshold(threshold,x,y+1)){
                    res++;
                    flags[x][y+1]=true;
                    queueX.add(x);
                    queueY.add(y+1);
                }
                if(x-1>=0&&(!flags[x-1][y])&&!overThreshold(threshold,x-1,y)){
                    res++;
                    flags[x-1][y]=true;
                    queueX.add(x-1);
                    queueY.add(y);
                }
                if(y-1>=0&&(!flags[x][y-1])&&!overThreshold(threshold,x,y-1)){
                    res++;
                    flags[x][y-1]=true;
                    queueX.add(x);
                    queueY.add(y-1);
                }
                size--;

            }
        }
        return res;
    }
    
    public boolean overThreshold(int threshold,int x,int y){
        int tmp = 0;
        while(x>0){
            tmp+=x%10;
            x/=10;
        }
        while(y>0){
            tmp+=y%10;
            y/=10;
        }
        return tmp>threshold;
    }