题目的链接在这里：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

目录

• 题目大意
• 一、示意图
• 二、解题思路
• • 递归
  • DFS
  • BFS

题目大意

一、示意图

二、解题思路

递归 DFS BFS

递归

代码如下：

class Solution {
      boolean [][] visited;
    //然后是记录格子数的吧
   // static int step;
    public  int movingCount(int m, int n, int k) {
        //直接初始化
        visited=new boolean[m][n];
        return dfs(0,0,visited,k,m,n);

    }
    //其实是使用了递归
    private  int dfs(int i, int j, boolean[][] visited, int k, int m, int n) {
        //然后这里开始判断
        if(i<0||i>=m||j<0||j>=n||(getNum(i)+getNum(j)>k)||visited[i][j]){
            //满足这个条件的 
            return 0;
        }
        //不然的话 就判断他的四周 并说明这个点本身就是可以的 还需要再加一
        visited[i][j]=true;
        return dfs(i+1,j,visited,k,m,n)+dfs(i-1,j,visited,k,m,n)+dfs(i,j+1,visited,k,m,n)+dfs(i,j-1,visited,k,m,n)+1;
    }

    private  int getNum(int i) {
        //要么就是写一个方法来求 i和j的数位合
  /*     if(i<10){
           return i;
       }*/
       if(i>=10&&i<=99){
          int temp1=i/10;
          int temp2=i%10;
          return temp1+temp2;
       }
       return i;
    }
}

DFS

代码如下：

class Solution {
    //坑定有个矩阵用来判断这个位置有没有走过
      boolean [][] visited;
     //然后是DFS
    int x[]={0,0,-1,1};
    int y[]={1,-1,0,0};
    int  count;
    public  int movingCount(int m, int n, int k) {
        //直接初始化
        visited=new boolean[m][n];
        count=0;
        //然后遍历第一个 并开始积累
        dfs(0,0,m,n,k,visited);
        return count;

    }

    private void dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        //先进行判断
        if(i>=m||j>=n)
            return;
        //然后判断是不是满足
        if(i>=0&&i<m&&j>=0&&j<n&&!visited[i][j]&&(getNum(i)+getNum(j)<=k)){
            //说明这个点是满足的
            count++;
            visited[i][j]=true;
            //然后遍历他的其他的 这边就不能用for循环
            for(int l=0;l<4;l++){
                dfs(i+x[l],j+y[l],m,n,k,visited);
            }
        }
    }

    private  int getNum(int i) {
        //要么就是写一个方法来求 i和j的数位合
  /*     if(i<10){
           return i;
       }*/
       if(i>=10&&i<=99){
          int temp1=i/10;
          int temp2=i%10;
          return temp1+temp2;
       }
       return i;
    }
}

BFS

代码如下：

class Solution {
    //坑定有个矩阵用来判断这个位置有没有走过
      boolean [][] visited;
     //然后是DFS
    int x[]={0,0,-1,1};
    int y[]={1,-1,0,0};
    int  count;
    public  int movingCount(int m, int n, int k) {
        //BFS的话 就是进栈 站内应该是一个 m和n组成的吧
        visited=new boolean[m][n];
        Queue<List<Integer>> queue=new LinkedList<>();
        List<Integer> list=new ArrayList<>();
        list.add(0);
        list.add(0);
        //然后就开始判断他周围的
        queue.add(list);
        count=0;
        visited[0][0]=true;
        while (!queue.isEmpty()){
            //取出栈顶元素
            List<Integer> poll = queue.poll();
            //然后取出栈顶元素中的两个值
            int i=poll.get(0);
            int j=poll.get(1);
          //  visited[i][j]=true;
            //然后count++ 每次出栈都记录一下就行了
            count++;
            //然后判断这个点的相邻点符不符合条件
            for(int l=0;l<4;l++){
                int new_i=i+x[l];
                int new_j=j+y[l];
                //然后进行判断
                if(new_i>=0&&new_i<m&&new_j>=0&&new_j<n&&!visited[new_i][new_j]&&(getNum(new_i)+getNum(new_j)<=k)){
                    //满足条件的话 就进队列
                    List<Integer> temp=new ArrayList<>();
                    //会导致 1 1出现两次 所有应该在这就设置为true
                    temp.add(new_i);
                    temp.add(new_j);
                    visited[new_i][new_j]=true;
                    queue.add(temp);
                }
            }

        }
        return count;

    }



    private  int getNum(int i) {
        //要么就是写一个方法来求 i和j的数位合
  /*     if(i<10){
           return i;
       }*/
       if(i>=10&&i<=99){
          int temp1=i/10;
          int temp2=i%10;
          return temp1+temp2;
       }
       return i;
    }
}