首页 > 试题广场 >

机器人移动范围

[编程题]机器人移动范围

热度指数：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 。请问该机器人能够达到多少个格子？

数据范围： $0 \le n , m \le 100 \$ ， $1 \le k \le 20 \$

输入描述:

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

输出描述:

一个正整数，代表该机器人能够到达的格子数量。

示例1

输入

3 3 6

输出

示例2

输入

1 1 1

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var m,n,k int
    fmt.Scan(&m,&n,&k)
    mat:=make([][]int,m)
    for i,_:=range mat{
        mat[i]=make([]int,n)
    }
    ans:=0
    var dfs func(int,int)
    dfs=func(i,j int){
        if i<0||i>=m||j<0||j>=n||mat[i][j]==1||calc(i,j)>k{
            return
        }
        mat[i][j]=1
        ans++
        dfs(i+1,j)
        dfs(i,j+1)
        dfs(i-1,j)
        dfs(i,j-1)
    }
    dfs(0,0)
    fmt.Print(ans)
}

func calc(i,j int)int{
    ans:=0
    for i>0{
        ans+=i%10
        i/=10
    }
    for j>0{
        ans+=j%10
        j/=10
    }
    return ans
}

发表于 2023-03-22 16:55:24 回复(0)