当前位置：首页 > news >正文

西安成品网站建设山东建站

news 2025/8/1 13:08:44

西安成品网站建设,山东建站,做博客网站最好用什么系统,盐城中瑞做网站公司题目描述宝宝和妈妈参加亲子游戏，在一个二维矩阵（NN）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。游戏规则是妈妈必须在最短的时间（每个单…

题目描述

宝宝和妈妈参加亲子游戏，在一个二维矩阵（NN）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
输入描述
第一行输入为N，N标识二维矩阵的大小
之后N行，每行有N个值，表格矩阵每个位置的值
其中：
-3：妈妈
-2：宝宝
-1：障碍
=0：糖果数(0表示没有糖果，但是可以走)
输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格
示例1
输入输出示例仅供调试，后台判题数据一般不包含示例
输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
输出
9
说明

此地图有两条最短路径可到宝宝位置，绿色线和黄色线都是最短路径6步，但黄色拿到的糖果更多，9个
示例2
输入输出示例仅供调试，后台判题数据一般不包含示例
输入
4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3
输出
-1
说明

此地图妈妈无法到达宝宝位置
备注
地图最大5050

解题思路

解题思路主要包括两个步骤：

寻找最短路径： 使用深度优先搜索（DFS）或广度优先搜索（BFS）来找到妈妈到宝宝位置的所有最短路径。在这个过程中，需要注意不走障碍物且避免重复访问同一个位置。在找到路径的同时，记录路径的长度。
计算最多糖果： 遍历所有找到的最短路径，计算每条路径上经过的糖果总数，选择最大的糖果总数作为结果。

以下是详细的解题思路：

从输入中读取地图大小 N 和地图矩阵 arr。
使用深度优先搜索（DFS）或广度优先搜索（BFS）找到妈妈到宝宝位置的最短路径。在搜索的过程中，记录路径的长度和路径上的所有点。
遍历所有找到的最短路径，计算每条路径上经过的糖果总数。
输出最大的糖果总数作为结果。

题解代码

Python题解代码

class PP:def __init__(self, x, y):self.x = xself.y = yg_pts = []  # 存储所有可能的路径
g_len = 30000  # 初始化最短路径长度
dx = [0, 0, 1, -1]  # 方向数组，用于搜索路径
dy = [1, -1, 0, 0]def get_path(arr, n, begin, end, p):global g_pts, g_lenif begin.x >= n or begin.x < 0 or begin.y >= n or begin.y < 0 or arr[begin.x][begin.y] == -1 or len(p) > g_len:return  # 越界或者访问过的位置直接返回p.append(begin)if begin.x == end.x and begin.y == end.y and len(p) <= g_len:g_pts.append(p[:])  # 找到一条路径，存储并更新最短路径长度g_len = len(p)returnold = arr[begin.x][begin.y]  # 保存当前位置的值arr[begin.x][begin.y] = -1  # 标记当前位置为已访问for i in range(4):x = begin.x + dx[i]y = begin.y + dy[i]get_path(arr, n, PP(x, y), end, p.copy())  # 递归搜索四个方向arr[begin.x][begin.y] = old  # 恢复当前位置的值if __name__ == "__main__":n = int(input())  # 读取输入的大小arr = []  # 存储迷宫begin = PP(0, 0)  # 起始位置end = PP(0, 0)  # 终点位置for i in range(n):row = list(map(int, input().split()))  # 读取每一行的数据arr.append(row)for j in range(n):if row[j] == -3:begin = PP(i, j)  # 记录起始位置elif row[j] == -2:end = PP(i, j)  # 记录终点位置tmp = []get_path(arr, n, begin, end, tmp)  # 搜索所有可能的路径mxv = -1if len(g_pts) > 0:for p in g_pts:if len(p) == g_len:  # 只考虑最短路径all = 0for i in range(1, len(p) - 1):all += arr[p[i].x][p[i].y]  # 计算路径上的数字总和if all > mxv:mxv = all  # 更新最大值print(mxv)  # 输出结果

JAVA题解代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;class PP {int x;int y;public PP(int _x, int _y) {x = _x;y = _y;}
}public class Main {static List<List<PP>> g_pts = new ArrayList<>();static int g_len = 30000;static int[] dx = {0, 0, 1, -1};static int[] dy = {1, -1, 0, 0};public static int getPath(int[][] arr, int n, PP begin, PP end, List<PP> p) {if (begin.x >= n || begin.x < 0 || begin.y >= n || begin.y < 0 || arr[begin.x][begin.y] == -1 || p.size() > g_len) {return 0;}p.add(begin);if (begin.x == end.x && begin.y == end.y && p.size() <= g_len) {g_pts.add(new ArrayList<>(p));g_len = p.size();return 0;}int old = arr[begin.x][begin.y];arr[begin.x][begin.y] = -1;for (int i = 0; i < 4; ++i) {int x = begin.x + dx[i];int y = begin.y + dy[i];getPath(arr, n, new PP(x, y), end, new ArrayList<>(p));}arr[begin.x][begin.y] = old;return 0;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[][] arr = new int[n][n];PP begin = new PP(0, 0);PP end = new PP(0, 0);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {arr[i][j] = scanner.nextInt();if (arr[i][j] == -3) {begin = new PP(i, j);} else if (arr[i][j] == -2) {end = new PP(i, j);}}}List<PP> tmp = new ArrayList<>();getPath(arr, n, begin, end, tmp);int mxv = -1;if (g_pts.size() > 0) {for (List<PP> p : g_pts) {if (p.size() == g_len) {int all = 0;for (int i = 1; i < p.size() - 1; ++i) {all += arr[p.get(i).x][p.get(i).y];}if (all > mxv) mxv = all;}}}System.out.println(mxv);}
}

C/C++题解代码

#include <iostream>
#include <queue>
#include <climits>
#include <vector>using namespace std;struct PP {int x;int y;PP(int _x, int _y) : x(_x), y(_y) {}
};const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };vector<vector<PP>> g_pts;
int g_len = 30000;
int getPath(vector<vector<int>>& arr, int n, PP begin, PP end, vector<PP> p) {if (begin.x >= n || begin.x < 0 || begin.y >= n || begin.y < 0 || arr[begin.x][begin.y] == -1 || p.size() > g_len) {return 0;}p.push_back(begin);if (begin.x == end.x && begin.y == end.y && p.size() <= g_len) {g_pts.push_back(p);g_len = p.size();return 0;}int old = arr[begin.x][begin.y];arr[begin.x][begin.y] = -1;for (int i = 0; i < 4; ++i) {int x = begin.x + dx[i];int y = begin.y + dy[i];getPath(arr, n, { x,y }, end, p);}arr[begin.x][begin.y] = old;return 0;
}int main() {int n;cin >> n;vector<vector<int>> arr(n, vector<int>(n));PP begin(0, 0);PP end(0, 0);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> arr[i][j];if (arr[i][j] == -3) {begin = { i, j };}else if (arr[i][j] == -2) {end = { i, j };}}}vector<PP> tmp;getPath(arr, n, begin, end, tmp);int mxv = -1;if (g_pts.size() > 0) {for (auto p : g_pts) {if (p.size() == g_len) {int all = 0;for (int i = 1; i < p.size() - 1; ++i) {all += arr[p[i].x][p[i].y];}if (all > mxv)mxv = all;}}}cout << mxv << endl;return 0;
}

JS题解代码


class Point {constructor(x, y) {this.x = x;this.y = y;}
}let gPts = [];  // 存储所有可能的路径
let gLen = 30000;  // 初始化最短路径长度const dx = [0, 0, 1, -1];  // 方向数组，用于搜索路径
const dy = [1, -1, 0, 0];function getPath(arr, n, begin, end, p) {if (begin.x >= n || begin.x < 0 || begin.y >= n || begin.y < 0 || arr[begin.x][begin.y] === -1 || p.length > gLen) {return;  // 越界或者访问过的位置直接返回}p.push(new Point(begin.x, begin.y));if (begin.x === end.x && begin.y === end.y && p.length <= gLen) {gPts.push([...p]);  // 找到一条路径，存储并更新最短路径长度gLen = p.length;return;}const old = arr[begin.x][begin.y];  // 保存当前位置的值arr[begin.x][begin.y] = -1;  // 标记当前位置为已访问for (let i = 0; i < 4; ++i) {const x = begin.x + dx[i];const y = begin.y + dy[i];getPath(arr, n, new Point(x, y), end, [...p]);  // 递归搜索四个方向}arr[begin.x][begin.y] = old;  // 恢复当前位置的值
}function main() {const n = parseInt(prompt());  // 读取输入的大小const arr = [];  // 存储迷宫let begin = new Point(0, 0);  // 起始位置let end = new Point(0, 0);  // 终点位置for (let i = 0; i < n; i++) {const row = prompt().split(' ').map(Number);  // 读取每一行的数据arr.push(row);for (let j = 0; j < n; j++) {if (row[j] === -3) {begin = new Point(i, j);  // 记录起始位置} else if (row[j] === -2) {end = new Point(i, j);  // 记录终点位置}}}const tmp = [];getPath(arr, n, begin, end, tmp);  // 搜索所有可能的路径let mxv = -1;if (gPts.length > 0) {for (const p of gPts) {if (p.length === gLen) {  // 只考虑最短路径let all = 0;for (let i = 1; i < p.length - 1; ++i) {all += arr[p[i].x][p[i].y];  // 计算路径上的数字总和}if (all > mxv) {mxv = all;  // 更新最大值}}}}console.log(mxv);  // 输出结果
}main();

代码OJ评判结果

通过测试点

代码讲解

Python 题解代码解析：

PP 类：
- 用于表示二维平面上的点，包含两个属性 x 和 y。
全局变量：
- g_pts: 用于存储所有可能的路径。
- g_len: 初始化最短路径长度为 30000。
- dx 和 dy: 方向数组，用于搜索路径。
get_path 函数：
- 使用深度优先搜索（DFS）找到妈妈到宝宝位置的所有最短路径。
- 参数包括迷宫数组 arr、迷宫大小 n、起始点 begin、终点 end、当前路径 p。
- 递归搜索所有可能的路径，并在找到最短路径时更新全局变量 g_pts 和 g_len。
主程序：
- 读取迷宫大小 n。
- 读取迷宫数组 arr。
- 使用 PP 类创建起始点 begin 和终点 end。
- 调用 get_path 函数搜索所有可能的路径。
- 遍历找到的最短路径，计算路径上的糖果总数，输出最大糖果总数。

JAVA 题解代码解析：

PP 类：
- 用于表示二维平面上的点，包含两个属性 x 和 y。
全局变量：
- g_pts: 用于存储所有可能的路径。
- g_len: 初始化最短路径长度为 30000。
- dx 和 dy: 方向数组，用于搜索路径。
getPath 函数：
- 使用深度优先搜索（DFS）找到妈妈到宝宝位置的所有最短路径。
- 参数包括迷宫数组 arr、迷宫大小 n、起始点 begin、终点 end、当前路径 p。
- 递归搜索所有可能的路径，并在找到最短路径时更新全局变量 g_pts 和 g_len。
主程序：
- 读取迷宫大小 n。
- 读取迷宫数组 arr。
- 使用 PP 类创建起始点 begin 和终点 end。
- 调用 getPath 函数搜索所有可能的路径。
- 遍历找到的最短路径，计算路径上的糖果总数，输出最大糖果总数。

C/C++ 题解代码解析：

PP 结构体：
- 用于表示二维平面上的点，包含两个属性 x 和 y。
全局变量：
- g_pts: 用于存储所有可能的路径。
- g_len: 初始化最短路径长度为 30000。
- dx 和 dy: 方向数组，用于搜索路径。
getPath 函数：
- 使用深度优先搜索（DFS）找到妈妈到宝宝位置的所有最短路径。
- 参数包括迷宫数组 arr、迷宫大小 n、起始点 begin、终点 end、当前路径 p。
- 递归搜索所有可能的路径，并在找到最短路径时更新全局变量 g_pts 和 g_len。
主程序：
- 读取迷宫大小 n。
- 读取迷宫数组 arr。
- 使用 PP 结构体创建起始点 begin 和终点 end。
- 调用 getPath 函数搜索所有可能的路径。
- 遍历找到的最短路径，计算路径上的糖果总数，输出最大糖果总数。

JS 题解代码解析：

Point 类：
- 用于表示二维平面上的点，包含两个属性 x 和 y。
全局变量：
- gPts: 用于存储所有可能的路径。
- gLen: 初始化最短路径长度为 30000。
- dx 和 dy: 方向数组，用于搜索路径。
getPath 函数：
- 使用深度优先搜索（DFS）找到妈妈到宝宝位置的所有最短路径。
- 参数包括迷宫数组 arr、迷宫大小 n、起始点 begin、终点 end、当前路径 p。
- 递归搜索所有可能的路径，并在找到最短路径时更新全局变量 gPts 和 gLen。
主程序：
- 通过 prompt 获取用户输入。
- 使用 Point 类创建起始点 begin 和终点 end。
- 调用 getPath 函数搜索所有可能的路径。
- 遍历找到的最短路径，计算路径上的糖果总数，输出最大糖果总数。