题目描述
宝宝和妈妈参加亲子游戏，在一个二维矩阵（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 = x
self.y = y
g_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_len
if 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)
return
old = 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 = -1
if len(g_pts) > 0:
for p in g_pts:
if len(p) == g_len: # 只考虑最短路径
all = 0
for 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函数搜索所有可能的路径。 - 遍历找到的最短路径，计算路径上的糖果总数，输出最大糖果总数。
- 通过