如果有不明白的请加文末QQ群。本文涉及知识点01最短路CBFS算法图论知识汇总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.lengthn grid[i].length1 m, n 10001最短路如果方向相同则距离为0否则为1。代码核心代码classSolution{public:intminCost(constvectorvectorintgrid){constintRgrid.size();constintCgrid[0].size();constintiMaskCountR*C;intmoves[][2]{{0,0},{0,1},{0,-1},{1,0},{-1,0}};intmaskAdd[]{0,1,-1,C,-C};vectorvectorintvNeiBo0(iMaskCount),vNeiBo1(iMaskCount);for(intr0;rR;r){for(intc0;cC;c){constintmaskC*rc;for(intmove1;move4;move){intr1rmoves[move][0];intc1cmoves[move][1];if((r10)||(r1R)||(c10)||(c1C)){continue;}autovNeiBo(grid[r][c]move)?vNeiBo0:vNeiBo1;vNeiBo[mask].emplace_back(maskmaskAdd[move]);}}}C01BFSDisbfs(vNeiBo0,vNeiBo1,0);returnbfs.m_vDis.back();}};单元测试templateclassT1,classT2voidAssertEx(constT1t1,constT2t2){Assert::AreEqual(t1,t2);}templateclassTvoidAssertEx(constvectorTv1,constvectorTv2){Assert::AreEqual(v1.size(),v2.size());for(inti0;iv1.size();i){Assert::AreEqual(v1[i],v2[i]);}}templateclassTvoidAssertV2(vectorvectorTvv1,vectorvectorTvv2){sort(vv1.begin(),vv1.end());sort(vv2.begin(),vv2.end());Assert::AreEqual(vv1.size(),vv2.size());for(inti0;ivv1.size();i){AssertEx(vv1[i],vv2[i]);}}namespaceUnitTest{vectorvectorintgrid;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){grid{{1,1,1,1},{2,2,2,2},{1,1,1,1},{2,2,2,2}};autoresSolution().minCost(grid);AssertEx(3,res);}TEST_METHOD(TestMethod01){grid{{1,1,3},{3,2,2},{1,1,4}};autoresSolution().minCost(grid);AssertEx(0,res);}TEST_METHOD(TestMethod02){grid{{1,2},{4,3}};autoresSolution().minCost(grid);AssertEx(1,res);}TEST_METHOD(TestMethod03){grid{{2,2,2},{2,2,2}};autoresSolution().minCost(grid);AssertEx(3,res);}TEST_METHOD(TestMethod04){grid{{4}};autoresSolution().minCost(grid);AssertEx(0,res);}};}扩展阅读我想对大家说的话亲士工具箱支持AutoCad2013及以上工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。