西安成品网站建设建站
题目描述
宝宝和妈妈参加亲子游戏，在一个二维矩阵（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函数搜索所有可能的路径。 - 遍历找到的最短路径，计算路径上的糖果总数，输出最大糖果总数。
- 通过
寄语
🚀✨ 朋友，希望你的华为OD机试就像是一场轻松的技术party！愿你的代码如同畅快的音符，跳跃在键盘上，最后弹奏出一曲高分之歌。加油，你是技术舞台上的巨星！通过机试，就像是风轻云淡，轻轻松松就把高分收入囊中。祝愿你的编程之旅一路顺风，破风前行，每一行代码都是成功的注脚！🌈💻
