网站后台怎么上传文章,软件公司有哪些部门,永久免费的连外网的软件,如何做收费会员定制网站#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ dijkstra(迪杰斯特拉) 求解思路 实现代码 运行结果 共勉 题目链接
2304. 网格中的最小路径代价
⛲ 题目描述
给你一个下标从 0 开始的整数矩阵 grid 矩阵大小为 m x n 由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) 且满足 x m - 1 你可以移动到 (x 1, 0), (x 1, 1), …, (x 1, n - 1) 中的任何一个单元格。注意 在最后一行中的单元格不能触发移动。
每次可能的移动都需要付出对应的代价代价用一个下标从 0 开始的二维数组 moveCost 表示该数组大小为 (m * n) x n 其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。
grid 一条路径的代价是所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发返回到达 最后一行 任意单元格的最小路径代价。
示例 1
输入grid [[5,3],[4,0],[2,1]], moveCost [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]] 输出17 解释最小代价的路径是 5 - 0 - 1 。
路径途经单元格值之和 5 0 1 6 。从 5 移动到 0 的代价为 3 。从 0 移动到 1 的代价为 8 。 路径总代价为 6 3 8 17 。 示例 2
输入grid [[5,1,2],[4,0,3]], moveCost [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]] 输出6 解释 最小代价的路径是 2 - 3 。
路径途经单元格值之和 2 3 5 。从 2 移动到 3 的代价为 1 。 路径总代价为 5 1 6 。
提示
m grid.length n grid[i].length 2 m, n 50 grid 由从 0 到 m * n - 1 的不同整数组成 moveCost.length m * n moveCost[i].length n 1 moveCost[i][j] 100 求解思路实现代码运行结果 ⚡ dijkstra(迪杰斯特拉) 求解思路
该题通过迪杰斯特拉算法求解即可但是需要注意的是我们需要找到一个开始的节点位置以及结束的位置因为题目中给定的是可以从第一行任意节点开始到达最后一行任意节点这个过程通过设置俩个虚拟的节点解决。其它的过程就是dijkstra基本求解过程。具体实现代码如下需要注意的是该题还可以通过dp来做后续补充。敬请期待。 实现代码
class Solution {public int minPathCost(int[][] grid, int[][] moveCost) {int mgrid.length,ngrid[0].length;int[][] mapnew int[m*n2][m*n2];for(int i0;imap.length;i) Arrays.fill(map[i],Integer.MAX_VALUE/2);int startm*n;for(int j0;jn;j){int togrid[0][j];map[start][to]0to;}for(int i0;im-1;i){for(int j0;jn;j){int fromgrid[i][j];for(int k0;kn;k){int togrid[i1][k];map[from][to]moveCost[from][k]to;}}}for(int j0;jn;j){int fromgrid[m-1][j];map[from][n*m1]0;}int[] ansdijkstra(grid,map,moveCost,start);for(int v:ans){System.out.println(v);}return ans[n*m1];}public int[] dijkstra(int[][] grid,int[][] map,int[][] moveCost,int start){int mgrid.length,ngrid[0].length;PriorityQueueint[] queuenew PriorityQueue((a,b)-a[1]-b[1]);queue.add(new int[]{start,0});boolean[] flagnew boolean[m*n2];Arrays.fill(flag,false);int[] distnew int[m*n2];Arrays.fill(dist,Integer.MAX_VALUE/2);dist[m*n]0;while(!queue.isEmpty()){int[] arrqueue.poll();int nextarr[0],costarr[1];if(flag[next]) continue;flag[next]true;for(int ne0;nem*n1;ne){if(map[next][ne]dist[next]dist[ne]){dist[ne]map[next][ne]dist[next];queue.add(new int[]{ne,dist[ne]});}}}return dist;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
