刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

编程实现：

在一个 M 行 N 列的网格中放有若干个坚果（一个小格子里最多放一个坚果），第 X 行 Y 列的小格子是小松鼠的家。

小松鼠可以向上下左右的格子移动寻找坚果，但它每次从家出发后，最多可以移动 K 个小格子，发现格子中有坚果，就会将其运回家储藏起来（运回家所移动的格子不做计算），然后再从家出发寻找其他坚果。小松鼠最多可以储藏几个坚果。

例如：M=7，N=6，X=3，Y=4，K=3，在 7 行 6 列的网格中有若干个坚果（如下图），小松鼠的家在第 3 行，第 4 列的位置，最多可以移动 3 个小格。

小松鼠最多可以储藏 7 个坚果（小格子底色为绿色的坚果）。

输入描述：

第一行输入两个正整数 M 和 N（2≤M≤30，1≤N≤30），表示 M 行 N 列的网格，两个正整数之间以一个英文逗号隔开；

第二行输入两个正整数 X 和 Y（1≤X≤M，1≤Y≤N），表示小松鼠家的位置在第 X 行第 Y 列，两个正整数之间以一个英文逗号隔开；

第三行输入一个正整数 K（1≤K≤max(M, N)-1），表示小松鼠从家出发后，最多可以移动的小格子数第四行开始，输入 M 行，每行 N 个整数，除了第 X 行 Y 列的小格子用 2 表示小松鼠的家，其他小格子的整数只能是 0 或者 1。0 表示小格子中没有坚果，1 表示小格子中有 1 个坚果，整数之间以一个英文逗号隔开。

输出描述：

输出一个整数，表示小松鼠最多可以储藏的坚果数量。


样例输入：

7,6
3,4
3
0,0,1,0,1,0
0,0,0,0,1,0
0,1,0,2,0,0
1,0,0,1,0,1
0,0,1,0,0,0
0,0,0,0,0,1
1,0,0,1,0,0

样例输出：

7

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythondef max_nuts(M, N, X, Y, K):grid = [[0] * N for _ in range(M)]for i in range(M):grid[i] = list(map(int, input().split()))visited = [[False] * N for _ in range(M)]visited[X-1][Y-1] = Truestack = [(X-1, Y-1)]nuts = 0directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]while stack:x, y = stack.pop()for dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < M and 0 <= ny < N and not visited[nx][ny] and abs(nx-x) + abs(ny-y) <= K:if grid[nx][ny] == 1:visited[nx][ny] = Truenuts += 1stack.append((nx, ny))return nutsM, N = map(int, input().split())X, Y = map(int, input().split())K = int(input())print(max_nuts(M, N, X, Y, K))```

解析：

【喵呜刷题小喵解析】：

本题是一个典型的广度优先搜索（BFS）问题。我们可以使用队列来实现BFS。

首先，我们定义一个二维数组grid来存储网格中的坚果，其中0表示没有坚果，1表示有一个坚果。

然后，我们定义一个二维数组visited来记录每个格子是否被访问过，初始时只有小松鼠的家被标记为已访问。

接着，我们定义一个队列stack，并将小松鼠的家作为起点加入队列。

然后，我们定义一个变量nuts来记录小松鼠最多可以储藏的坚果数量，初始值为0。

最后，我们定义一个变量directions来存储四个方向的偏移量，即上、下、左、右。

在BFS的过程中，我们每次从队列中取出一个格子，然后遍历其四个相邻的格子。如果相邻的格子没有被访问过，且小松鼠可以到达该格子（即小松鼠从家出发后，最多可以移动的小格子数不超过K），则将该格子加入队列，并将其标记为已访问。如果该格子中有坚果，则将该格子中的坚果数量加入nuts。

最后，我们返回nuts即为小松鼠最多可以储藏的坚果数量。
创作类型：
原创

本文链接：编程实现： 在一个 M 行 N 列的网格中放有若干个坚果（一个小格子里最多放一个坚果），第 X 行

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share