首页 > 试题广场 >

机器人移动范围

[编程题]机器人移动范围
  • 热度指数：4547 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
地上有一个 m 行和 n 列的方格。一个机器人从坐标 0,0 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 例如，当 k 为 18 时，机器人能够进入方格（35,37），因为 3+5+3+7 = 18 。但是，它不能进入方格（35,38），因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

数据范围： ，

输入描述:
一行三个正整数由空格分开，分别代表行数 m ，列数 n ，和坐标数位之和的阈值 k 。


输出描述:
一个正整数，代表该机器人能够到达的格子数量。
示例1

输入

3 3 6

输出

9
示例2

输入

1 1 1

输出

1
算法知识视频讲解
添加回答
Java
喜欢吃火锅的三文鱼希望被offer砸中头像 喜欢吃火锅的三文鱼希望被offer砸中 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] numStr = sc.nextLine().split(" ");
        
        int m = Integer.valueOf(numStr[0]);
        int n = Integer.valueOf(numStr[1]);
        int k = Integer.valueOf(numStr[2]);
        
        int[][] grid = new int[m][n];
        int nums = dfs(grid, 0, 0, m, n, k);
        
        System.out.println(nums);
    }
    
    public static int dfs(int[][] grid, int row, int col, int m, int n, int k) {
        if (row < 0 || row >= m || col < 0 || col >= n) return 0;
        
        if (getSum(row) + getSum(col) > k || grid[row][col] == 1) return 0;
        
        grid[row][col] = 1;
        
        return 1 + dfs(grid, row - 1, col, m, n, k) 
                 + dfs(grid, row + 1, col, m, n, k)
                 + dfs(grid, row, col - 1, m, n, k)
                 + dfs(grid, row, col + 1, m, n, k);
        
    }
    
    public static int getSum(int point) {
        int sum = 0;
        while (point != 0) {
            sum += (point % 10);
            point /= 10;
        }
        
        return sum;
    }
}

发表于 2022-08-28 09:41:13 回复(0)
Java
嘤嘤嘤？啊哈头像 嘤嘤嘤？啊哈 
import java.util.*;
public class Main{
    private static int[][] step={{0,1},{-1,0},{0,-1},{1,0}};
    private static int cnt=0;
    private static boolean isBigger(int r,int c,int k)
    {
        int res=0;
        while(r>0)
        {
            res+=r%10;
            r/=10;
        }
        while(c>0)
        {
            res+=c%10;
            c/=10;
        }
        if(res>k)
            return true;
        return false;
    }
    public static void backTrack(int i,int j,int k,int rows,int cols,boolean[][] mark){
        if(i>=rows||i<0||j>=cols||j<0||mark[i][j])
            return;
        mark[i][j]=true;
        if(isBigger(i,j,k))
            return;
        cnt++;
        for(int[] n:step)
            backTrack(i+n[0],j+n[1],k,rows,cols,mark);
        
    }
    public static void main(String args[]){
        Scanner scan=new Scanner(System.in);
        int m=scan.nextInt();
        int n=scan.nextInt();
        int k=scan.nextInt();
        boolean[][] mark=new boolean[m][n];
        backTrack(0,0,k,m,n,mark);
        System.out.println(cnt);
    }
}

发表于 2020-05-26 15:35:03 回复(0)
Java
老泉1248头像 老泉1248
importjava.util.Scanner;
publicclassMain{
    privatestaticintm, n;
    privatestaticint[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    publicstaticvoidmain(String[] args){
        Scanner sc = newScanner(System.in);
        String s = sc.nextLine();
        String sub[] = s.split(" ");
        m = Integer.valueOf(sub[0]);
        n = Integer.valueOf(sub[1]);
        intk = Integer.valueOf(sub[2]);
        booleanvisited[][] = newboolean[m][n];
        intgezi = 1;
        intres = getCount(0, 0, k, visited, gezi);
        System.out.println(res);
    }
     
    privatestaticintgetCount(intmm, intnn, intk, boolean[][] visited, intgezi){
        if(mm >= m || mm < 0|| nn >= n || nn < 0|| visited[mm][nn]){
            return0;
        }
        intwei = 0;
        String mw = String.valueOf(mm);
        String nw = String.valueOf(nn);
        for(inti = 0; i < mw.length(); i++){
            wei += Integer.valueOf(mw.charAt(i)-'0');
        }
        for(inti = 0; i < nw.length(); i++){
            wei += Integer.valueOf(nw.charAt(i)-'0');
        }
        if(wei > k){
            return0;
        }
        visited[mm][nn] = true;
        //int count = 1;
        for(int[] d: direction){
            intnextm = mm + d[0];
            intnextn = nn + d[1];
            gezi = Math.max(gezi, getCount(nextm, nextn, k, visited, gezi + 1));
        }
        return gezi;
    }
}
发表于 2020-03-20 23:06:30 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 快手 数组 运维工程师 前端工程师 算法工程师 测试工程师 图 PHP工程师 2019 数学 Java工程师
上传者：小小
难度：
3条回答 6987浏览

热门推荐

通过挑战的用户

查看代码

相关试题

机器人移动范围

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号