首页 > 试题广场 >

地鼠逃跑计划

[编程题]地鼠逃跑计划

热度指数：3423 时间限制：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

输入

输出

算法知识视频讲解

Python

LitterF

背包算法，一次次往里放进行了，把落在边上的数一下就行了

复杂度O(mnk)。空间复杂度O(mn2)，用了滚动优化，总共是2*m*n。实际上两维m,n还可以优化到一维。

m = int(input())
n = int(input())
x = int(input()) + 1
y = int(input()) + 1
K = int(input())
def sum_round(data):
    cur = 0
    row,col = len(data),len(data[0])
    for i in range(row):
        for j in range(col):
            if i==0 or j == 0 or i==row-1 or j==col-1:
                cur+=data[i][j]
    return cur
data = []
for _ in range(m+2):
    data.append([0 for _ in range(n+2)])
res = [[],[]]
import copy
res[0]=copy.deepcopy(data)
res[1]=copy.deepcopy(data)
res[0][x][y]=1
cur = 0
for k in range(1,K+1):
    res[k%2] = copy.deepcopy(data)
    for i in range(1,m+1):
        for j in range(1,n+1):
            res[k%2][i+1][j] += res[k%2-1][i][j]
            res[k%2][i-1][j] += res[k%2-1][i][j]
            res[k%2][i][j+1] += res[k%2-1][i][j]
            res[k%2][i][j-1] += res[k%2-1][i][j]
    cur+=sum_round(res[k%2])
print(cur)

发表于 2019-11-12 17:52:19 回复(1)

Python

ElonB

""""
BFS或DFS
"""
import sys
from collections import deque


def BFS(m, n, x, y, K):
    deq = deque([(x, y, 0)])
    ans = 0
    while deq:
        i, j, k = deq.popleft()
        if k >= K: break
        if i + 1 >= m:
            ans += 1
        else:
            deq.append((i + 1, j, k + 1))
        if i - 1 < 0:
            ans += 1
        else:
            deq.append((i - 1, j, k + 1))
        if j + 1 >= n:
            ans += 1
        else:
            deq.append((i, j + 1, k + 1))
        if j - 1 < 0:
            ans += 1
        else:
            deq.append((i, j - 1, k + 1))
    return ans


if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    m, n, x, y, K = int(input()), int(input()), int(input()), int(input()), int(input()),
    ans = BFS(m, n, x, y, K)
    print(ans)

发表于 2019-07-14 10:20:03 回复(0)