首页 > 试题广场 >

地鼠逃跑计划

[编程题]地鼠逃跑计划

热度指数：3429 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有一只地鼠不小心跑进了一个m*n的矩形田地里，假设地鼠在这块田地的初始位置为（x,y），并且每次只能向相邻的上下左右四个方向移动一步，那么在最多移动K次的情况下，有多少条路径可以逃出这片田地（一旦出去田地的边界就不能再往回走）？
下面是样例示意图：

输入描述:

输入数据包括五个参数：m,n,x,y,K
其中m和n的范围均为是[1,10]，K的范围是[0,10]。
0<=x<m,0<=y<n。

输出描述:

输出成功逃跑的路径数量。

示例1

输入

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var m,n,x,y,k int
    fmt.Scan(&m,&n,&x,&y,&k)
    ans:=0
    var dfs func(int,int,int)
    dfs=func(i,j int,tot int){
        if tot>k{
            return
        }
        if (i<0||i>=m||j<0||j>=n)&&tot<=k{
            ans++
            return
        }
        tot++
        dfs(i+1,j,tot)
        dfs(i-1,j,tot)
        dfs(i,j+1,tot)
        dfs(i,j-1,tot)
    }
    dfs(x,y,0)
    fmt.Print(ans)
}

发表于 2023-03-19 07:56:33 回复(0)