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

【01最短路 BFS】1368. 使网格图至少有一条有效路径的最小代价

news 2026/5/11 23:12:35

如果有不明白的，请加文末QQ群。

本文涉及知识点

01最短路
C++BFS算法
图论知识汇总

LeetCode 1368. 使网格图至少有一条有效路径的最小代价

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
注意网格图中可能会有无效数字，因为它们可能指向 grid 以外的区域。
一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条有效路径为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径不需要是最短路径。
你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字只能修改一次。
请你返回让网格图至少有一条有效路径的最小代价。
示例 1：
输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出：3
解释：你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)
总花费为 cost = 3.
示例 2：
输入：grid = [[1,1,3],[3,2,2],[1,1,4]]
输出：0
解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。
示例 3：
输入：grid = [[1,2],[4,3]]
输出：1
示例 4：
输入：grid = [[2,2,2],[2,2,2]]
输出：3
示例 5：
输入：grid = [[4]]
输出：0
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100

01最短路

如果方向相同，则距离为0；否则为1。

代码

核心代码

classSolution{public:intminCost(constvector<vector<int>>&grid){constintR=grid.size();constintC=grid[0].size();constintiMaskCount=R*C;intmoves[][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}};intmaskAdd[]={0,1,-1,C,-C};vector<vector<int>>vNeiBo0(iMaskCount),vNeiBo1(iMaskCount);for(intr=0;r<R;r++){for(intc=0;c<C;c++){constintmask=C*r+c;for(intmove=1;move<=4;move++){intr1=r+moves[move][0];intc1=c+moves[move][1];if((r1<0)||(r1>=R)||(c1<0)||(c1>=C)){continue;}auto&vNeiBo=(grid[r][c]==move)?vNeiBo0:vNeiBo1;vNeiBo[mask].emplace_back(mask+maskAdd[move]);}}}C01BFSDisbfs(vNeiBo0,vNeiBo1,0);returnbfs.m_vDis.back();}};

单元测试

template<classT1,classT2>voidAssertEx(constT1&t1,constT2&t2){Assert::AreEqual(t1,t2);}template<classT>voidAssertEx(constvector<T>&v1,constvector<T>&v2){Assert::AreEqual(v1.size(),v2.size());for(inti=0;i<v1.size();i++){Assert::AreEqual(v1[i],v2[i]);}}template<classT>voidAssertV2(vector<vector<T>>vv1,vector<vector<T>>vv2){sort(vv1.begin(),vv1.end());sort(vv2.begin(),vv2.end());Assert::AreEqual(vv1.size(),vv2.size());for(inti=0;i<vv1.size();i++){AssertEx(vv1[i],vv2[i]);}}namespaceUnitTest{vector<vector<int>>grid;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){grid={{1,1,1,1},{2,2,2,2},{1,1,1,1},{2,2,2,2}};autores=Solution().minCost(grid);AssertEx(3,res);}TEST_METHOD(TestMethod01){grid={{1,1,3},{3,2,2},{1,1,4}};autores=Solution().minCost(grid);AssertEx(0,res);}TEST_METHOD(TestMethod02){grid={{1,2},{4,3}};autores=Solution().minCost(grid);AssertEx(1,res);}TEST_METHOD(TestMethod03){grid={{2,2,2},{2,2,2}};autores=Solution().minCost(grid);AssertEx(3,res);}TEST_METHOD(TestMethod04){grid={{4}};autores=Solution().minCost(grid);AssertEx(0,res);}};}

扩展阅读

我想对大家说的话
亲士工具箱：支持AutoCad2013及以上
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。