营销网站建设创意,wordpress底部美化,休闲采摘园网站建设,厂字形网页布局网站题目描述 宝宝和妈妈参加亲子游戏#xff0c;在一个二维矩阵#xff08;NN#xff09;的格子地图上#xff0c;宝宝和妈妈抽签决定各自的位置#xff0c;地图上每个格子有不同的糖果数量#xff0c;部分格子有障碍物。 游戏规则是妈妈必须在最短的时间#xff08;每个单…题目描述 宝宝和妈妈参加亲子游戏在一个二维矩阵NN的格子地图上宝宝和妈妈抽签决定各自的位置地图上每个格子有不同的糖果数量部分格子有障碍物。 游戏规则是妈妈必须在最短的时间每个单位时间只能走一步到达宝宝的位置路上的所有糖果都可以拿走不能走障碍物的格子只能上下左右走。 请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果优先考虑最短时间到达的情况下尽可能多拿糖果。 输入描述 第一行输入为NN标识二维矩阵的大小 之后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 ListListPP 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, ListPP 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);}}}ListPP tmp new ArrayList();getPath(arr, n, begin, end, tmp);int mxv -1;if (g_pts.size() 0) {for (ListPP 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 vectorusing 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 };vectorvectorPP g_pts;
int g_len 30000;
int getPath(vectorvectorint arr, int n, PP begin, PP end, vectorPP 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;vectorvectorint arr(n, vectorint(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 };}}}vectorPP 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愿你的代码如同畅快的音符跳跃在键盘上最后弹奏出一曲高分之歌。加油你是技术舞台上的巨星通过机试就像是风轻云淡轻轻松松就把高分收入囊中。祝愿你的编程之旅一路顺风破风前行每一行代码都是成功的注脚
