【动态规划】【广度优先搜索】【逆向思考】【单调向量】2617 网格图中最少访问的格子数

本文涉及的基础知识点二分查找算法合集动态规划汇总题目给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。当你在格子 (i, j) 的时候你可以移动到以下格子之一满足 j k grid[i][j] j 的格子 (i, k) 向右移动或者满足 i k grid[i][j] i 的格子 (k, j) 向下移动。请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数如果无法到达右下角格子请你返回 -1 。示例 1输入grid [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]输出4解释上图展示了到达右下角格子经过的 4 个格子。示例 2输入grid [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]输出3解释上图展示了到达右下角格子经过的 3 个格子。示例 3输入grid [[2,1,0],[1,0,0]]输出-1解释无法到达右下角格子。参数范围m grid.lengthn grid[i].length1 m, n 1051 m * n 1050 grid[i][j] m * ngrid[m - 1][n - 1] 02024年2月3 总结一广度优先搜索。前置状态可以直接确定后置状态。难点每个后置状态只更新一次。a用有序映射。b用并集查找。二正向动态规格。枚举后置状态优先队列记录可能的合法前者状态。三逆向动态规划。枚举后置状态单调记录可能的合法前者状态。除用并集查找时间复杂度是:O(nm)外其它都是O(nm(logmlogn)。广度优先搜索和二分查找时间复杂度O(mnlogmax(m,n))。遍历每个单格时间复杂度O(nm)处理一个单格O(n)O(m)。暴力方法的时间复杂度O(nmk)极端情况下超时。变量解析vRows各行没有处理的单格的列号vCols各列没有处理的单格行号vDis各单格距离起点的距离que需要处理邻居的单格核心代码class Solution {public:int minimumVisitedCells(vectorvector grid) {m_r grid.size();m_c grid.front().size();vectorset vRows(m_r), vCols(m_c);for (int r 0; r m_r; r){for (int c 0; c m_c; c){if (r c 0){continue;}vRows[r].emplace©;vCols[c].emplace®;}}vector vDis(m_c * m_r,-1);vDis[0] 1;queuepairint, int que;que.emplace(0, 0);auto Do [](int iDis,const int r, const int c){vDis[m_c * r c] iDis 1;que.emplace(r, c);};while (que.size()){const auto [r, c] que.front();que.pop();const int len grid[r][c];const int dis vDis[m_c * r c];{//右跳auto it vRows[r].lower_bound©;auto ij vRows[r].upper_bound(c len);for (auto tmp it; tmp ! ij; tmp){Do(dis, r, *tmp);vCols[*tmp].erase®;}vRows[r].erase(it, ij);}{auto it vCols[c].lower_bound®;auto ij vCols[c].upper_bound(r len);for (auto tmp it; tmp ! ij; tmp){Do(dis, *tmp,c);vRows[*tmp].erase©;}vCols[c].erase(it, ij);}}return vDis.back();}int m_r, m_c;};测试用例templateclassTvoidAssert(constvectorTv1,constvectorTv2){if(v1.size()!v2.size()){assert(false);return;}for(inti0;iv1.size();i){assert(v1[i]v2[i]);}}templateclassTvoidAssert(constTt1,constTt2){assert(t1t2);}intmain(){vectorvectorintgrid;{Solution slu;grid{{3,4,2,1},{4,2,3,1},{2,1,0,0},{2,4,0,0}};autoresslu.minimumVisitedCells(grid);Assert(4,res);}{Solution slu;grid{{3,4,2,1},{4,2,1,1},{2,1,1,0},{3,4,1,0}};autoresslu.minimumVisitedCells(grid);Assert(3,res);}{Solution slu;grid{{2,1,0},{1,0,0}};autoresslu.minimumVisitedCells(grid);Assert(-1,res);}}动态规划广度优先搜索是基于动态规划实现的如果不修改广度优先的实现无需突出动态规划。经典广度优先搜索时先处理距离起点近的再处理距离远点的。是为了保证动态规划的无后效性。通俗的说就是每个运算的前提条件都已经计算完毕。距离为iDis的单格显然是距离iDis-1单格的邻居计算iDis的单格时显然要计算完所有距离为iDis-1的单格。本题只右移和下移先行后列行列都是从小到大也可以保证无后效性。优化枚举顺序后就不再是广度优先搜索了变成的普通的动态规划。时间复杂度O(mnlogmax(n,m))。变量解析rowMinHeap当前行可以到达的列和总共经过的单格数-1colMinHeaps各列可以到达的行和总共经过的单格数-1用小根堆记录经过的单格数和列号。由于列号是增加的所有如果堆顶的列号小于当前列号则对应小于后面的列号可以永久删除。 删除堆顶列号过小的元素后堆顶元素就是最小经过的单格。代码classSolution{public:typedefpriority_queuepairint,int,vectorpairint,int,greaterHTYPE;intminimumVisitedCells(vectorvectorintgrid){m_rgrid.size();m_cgrid.front().size();vectorvectorintvDis(m_r,vectorint(m_c,-1));vectorHTYPEcolMinHeaps(m_c);for(intr0;rm_r;r){HTYPE rowMinHeap;autoAdd[](constintr,constintc,intiNewDis){vDis[r][c]iNewDis;rowMinHeap.emplace(iNewDis,cgrid[r][c]);colMinHeaps[c].emplace(iNewDis,rgrid[r][c]);};for(intc0;cm_c;c){if(rc0){Add(r,c,1);continue;}while(rowMinHeap.size()(rowMinHeap.top().secondc)){rowMinHeap.pop();}while(colMinHeaps[c].size()(colMinHeaps[c].top().secondr)){colMinHeaps[c].pop();}intiPreMinINT_MAX;if(rowMinHeap.size()){iPreMinmin(iPreMin,rowMinHeap.top().first);}if(colMinHeaps[c].size()){iPreMinmin(iPreMin,colMinHeaps[c].top().first);}if(INT_MAXiPreMin){continue;}Add(r,c,iPreMin1);}}returnvDis.back().back();}intm_r,m_c;};单调向量有序向量)可以逆向考虑从终点到起点。这样可以记录可以到达单元格的行列和经过的单格数。在保持数据的单调的情况下行列递减单格数递增。新增有利条件 行列插入的顺序也递减。这意味者可以用单调向量。代码classSolution{public:intminimumVisitedCells(vectorvectorintgrid){m_rgrid.size();m_cgrid.front().size();vectorvectorintvDis(m_r,vectorint(m_c,-1));vectorvectorpairint,intcols(m_c);//列行号按降序排除距离按升序排列for(intrm_r-1;r0;r--){vectorpairint,introw;autoAdd[](constintr,constintc,intiNewDis){vDis[r][c]iNewDis;while(row.size()(row.back().firstiNewDis)){row.pop_back();}row.emplace_back(iNewDis,c);while(cols[c].size()(cols[c].back().firstiNewDis)){cols[c].pop_back();}cols[c].emplace_back(iNewDis,r);};autoCmp[](constpairint,intpr,intrc){returnpr.secondrc;};for(intcm_c-1;c0;c--){if(rc2m_rm_c){Add(r,c,1);continue;}intiPreMinINT_MAX;autoitstd::lower_bound(row.begin(),row.end(),cgrid[r][c],Cmp);if(row.end()!it){iPreMinmin(iPreMin,it-first);}autoijstd::lower_bound(cols[c].begin(),cols[c].end(),rgrid[r][c],Cmp);if(cols[c].end()!ij){iPreMinmin(iPreMin,ij-first);}if(INT_MAXiPreMin){continue;}Add(r,c,iPreMin1);}}returnvDis.front().front();}intm_r,m_c;};2023年8月版typedef std::priority_queuestd::pairint, int,vectorstd::pairint, int,std::greaterstd::pairint, int QUE;class Solution {public:int minimumVisitedCells(vectorvector grid) {m_r grid.size();m_c grid[0].size();vectorvector vVis(m_r, vector(m_c,INT_MAX));vVis[0][0] 1;vector std::multiset setCols(m_c);vector QUE vDelCols(m_c);for (int r 0; r m_r; r){for (int c 0; c m_c; c){auto setCol setCols[c];auto vDelCol vDelCols[c];while (vDelCol.size() (vDelCol.top().first r)){setCol.erase(setCol.find(vDelCol.top().second));vDelCol.pop();}}std::multiset setRow;QUE vDelRow;auto Add [](int r, int c, int dis, int value){if (INT_MAX dis){return;}setRow.emplace(dis);vDelRow.emplace(c value 1, dis);setCols[c].emplace(dis);vDelCols[c].emplace(r value 1, dis);};for (int c 0; c m_c; c){if (r c 0){Add(0, 0, vVis[0][0], grid[r][c]);continue;}while (vDelRow.size() (vDelRow.top().first c)){setRow.erase(setRow.find(vDelRow.top().second));vDelRow.pop();}if (setRow.size()){vVis[r][c] min(vVis[r][c],*setRow.begin()1);}auto setCol setCols[c];if (setCol.size()){vVis[r][c] min(vVis[r][c], *setCol.begin() 1);}if (INT_MAX vVis[r][c]){continue;}Add(r, c, vVis[r][c], grid[r][c]);}}int iRet vVis.back().back();return (INT_MAX iRet) ? -1 : iRet;}int m_r, m_c;};其它方法可以用有向图并集查找寻找没有删除的元素。r1和r2连接表示[r1,r2)已经全部删除直接处理r2。2023年9月版class Solution {public:int minimumVisitedCells(vectorvector grid) {m_r grid.size(), m_c grid[0].size();if (m_r * m_c 1){return 1;}vectorvectorstd::pairint,int vvRowMinDis(m_c); // 每列的单调栈int iRet m_iNotMay;for (int r m_r - 1; r 0; r–){std::vectorstd::pairint, int vColMinDis;//列号越来越小值越来越大for (int c m_c - 1; c 0; c–){auto sta vvRowMinDis[c];if ((m_r - 1 r) (m_c - 1 c)){vColMinDis.emplace_back(c, 1);sta.emplace_back(r, 1);continue;}int iCurDis m_iNotMay;//处理右移auto it std::lower_bound(vColMinDis.begin(), vColMinDis.end(), c grid[r][c], [](const std::pairint, int p1, int a){return p1.first a; });if (vColMinDis.end() ! it){const int iDis it-second 1;iCurDis min(iCurDis, iDis);}//处理左移auto ij std::lower_bound(sta.begin(), sta.end(), r grid[r][c], [](const std::pairint, int p1, int a){return p1.first a; });if (sta.end() ! ij){const int iDis ij-second 1;iCurDis min(iCurDis, iDis);}if (m_iNotMay iCurDis){continue;}while (sta.size() (sta.back().second iCurDis)){sta.pop_back();}sta.emplace_back(r, iCurDis);while (vColMinDis.size() (vColMinDis.back().second iCurDis)){vColMinDis.pop_back();}vColMinDis.emplace_back(c, iCurDis);if (r c 0){iRet iCurDis;}}}return (iRet m_iNotMay ) ? -1 : iRet;}int m_r, m_c;const int m_iNotMay 1000 * 1000 * 1000;};扩展阅读我想对大家说的话亲士工具箱支持AutoCad2013及以上工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。