题目链接

题目链接

题目描述

地上有一个 m 行和 n列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

注意:
0<=m<=50
0<=n<=50
0<=k<=100

样例1 输入：k=7, m=4, n=5 输出：20

样例2 输入：k=18, m=40, n=40 输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

题目考察知识点

图论！
深搜or光搜
当前节点可以达到的节点为上下左右四个方向

解题代码

深搜dfs

递归实现

java">class Solution {
    // 深度优先
    // 在确定完是否满足条件后，[先加结果，然后标为已走]，然后再进行dfs
    
    int result;
    // 可以走的方向
    int dir[][] = {{-1,0},{1,0},{0,1},{0,-1}};
    public int movingCount(int threshold, int rows, int cols)
    {
        // 判断临界情况，也就是rows和cols都为0
        if(rows == 0 || cols == 0){
            return 0;
        }
        
        // 判断是否走过
        boolean[][] used = new boolean[rows][cols];
        result = 0;
        
        // 判断0,0是否符合条件
        if(!judge(0,0,threshold))   return 0;
        
        result ++;
        used[0][0] = true;
        dfs(0, 0, rows, cols, threshold, used);
        return result;
    }
    
    // 深度优先
    public void dfs(int inow, int jnow, int rows, int cols, int threshold, boolean[][] used){
        for(int i = 0; i < 4; i ++){
            int inext = inow + dir[i][0];
            int jnext = jnow + dir[i][1];
            if(inext >= 0 && inext < rows && jnext >=0 && jnext < cols){
                // 满足条件，才进行下一个dfs
                if(used[inext][jnext]==false && judge(inext, jnext, threshold)){
                    result ++;
                    used[inext][jnext] = true;
                    dfs(inext, jnext, rows, cols, threshold, used);
                }
            }
        }
    }
    
    // 是否满足条件
    public boolean judge(int i, int j, int threshold){
        int now = 0;
        while(i != 0){
            now += i % 10;
            i = i / 10;
        }
        while(j != 0){
            now += j % 10;
            j = j / 10;
        }
        // 不满足
        if(now > threshold){
            return false;
        }else{
            return true;
        }
    }
}

注意注意！！！

• used数组是必须要有的！标识一下当前哪些格子被判断过了
• 判断临界条件
  • 特别是！哪个rows和cols都为0的情况
• 判断完是否符合条件再去进行dfs更容易

广搜bfs

队列实现
队列不为空的时候一直循环
符合条件的进入队列

java">class Solution {
    // 广度优先
    // 在确定完是否满足条件后，[先加结果，然后标为已走]，然后再进队列
    
    int result;
    // 可以走的方向
    int dir[][] = {{-1,0},{1,0},{0,1},{0,-1}};
    public int movingCount(int threshold, int rows, int cols)
    {
        // 判断临界情况，也就是rows和cols都为0
        if(rows == 0 || cols == 0){
            return 0;
        }
        
        // 判断是否走过
        boolean[][] used = new boolean[rows][cols];
        result = 0;
        
        bfs(rows, cols, threshold, used);
        return result;
    }
    
    // 广度优先
    public void bfs(int rows, int cols, int threshold, boolean[][] used){
        Deque<int[]> deque = new LinkedList<>();
        
        if(judge(0, 0, threshold)){
            deque.push(new int[]{0, 0});
            used[0][0] = true;
            result ++;
        }
        
        while(!deque.isEmpty()){
            int[] now = deque.pop();
            int inow = now[0];
            int jnow = now[1];
            for(int i = 0; i < 4; i ++){
                int inext = inow + dir[i][0];
                int jnext = jnow + dir[i][1];
                if(inext >= 0 && inext < rows && jnext >=0 && jnext < cols){
                    // 满足条件，才进入队列
                    if(used[inext][jnext]==false && judge(inext, jnext, threshold)){
                        result ++;
                        used[inext][jnext] = true;
                        deque.push(new int[]{inext, jnext});
                    }
                }
            }
        }
        return;
    }
    
    // 是否满足条件
    public boolean judge(int i, int j, int threshold){
        int now = 0;
        while(i != 0){
            now += i % 10;
            i = i / 10;
        }
        while(j != 0){
            now += j % 10;
            j = j / 10;
        }
        // 不满足
        if(now > threshold){
            return false;
        }else{
            return true;
        }
    }
}