【动态规划】【广度优先搜索】LeetCode: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.length

n == grid[i].length

1 <= m, n <= 10⁵

1 <= m * n <= 10⁵

0 <= grid[i][j] < m * n

grid[m - 1][n - 1] == 0

广度优先搜索和二分查找

时间复杂度

O(mnlogmax(m,n))。遍历每个单格时间复杂度O(nm)，处理一个单格O(n)+O(m)。暴力方法的时间复杂度O(nmk)，极端情况下超时。

变量解析

vRows	各行没有处理的单格的列号
vCols	各列没有处理的单格行号
vDis	各单格距离起点的距离
que	需要处理邻居的单格

核心代码

class Solution {

public:

int minimumVisitedCells(vector& grid) {

m_r = grid.size();

m_c = grid.front().size();

vector 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;

queue> 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;

};

测试用例

templatevoid Assert(const vector& v1, const vector& v2)
{if (v1.size() != v2.size())
	{assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{assert(v1[i] == v2[i]);
	}
}
templatevoid Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}
int main()
{vector> grid;
	{Solution slu;
		grid = { {3,4,2,1},{4,2,3,1},{2,1,0,0},{2,4,0,0} };
		auto res = slu.minimumVisitedCells(grid);
		Assert(4, res);
	}
	{Solution slu;
		grid = { {3,4,2,1},{4,2,1,1},{2,1,1,0},{3,4,1,0} };
		auto res = slu.minimumVisitedCells(grid);
		Assert(3, res);
	}
	{Solution slu;
		grid = { {2,1,0},{1,0,0} };
		auto res = slu.minimumVisitedCells(grid);
		Assert(-1, res);
	}
}

动态规划

广度优先搜索是基于动态规划实现的，如果不修改广度优先的实现，无需突出动态规划。经典广度优先搜索时，先处理距离起点近的，再处理距离远点的。是为了保证动态规划的无后效性。通俗的说：就是每个运算的前提条件都已经计算完毕。距离为iDis的单格显然是距离iDis-1单格的邻居，计算iDis的单格时，显然要计算完所有距离为iDis-1的单格。本题只右移和下移，先行后列，行列都是从小到大，也可以保证无后效性。优化枚举顺序后，就不再是广度优先搜索了，变成的普通的动态规划。

时间复杂度

O(mnlogmax(n,m))。

变量解析

rowMinHeap	当前行可以到达的列和总共经过的单格数-1
colMinHeaps	各列可以到达的行和总共经过的单格数-1

用小根堆记录经过的单格数和列号。由于列号是增加的，所有如果堆顶的列号小于当前列号，则对应小于后面的列号，可以永久删除。 删除堆顶列号过小的元素后，堆顶元素就是最小经过的单格树。

代码

class Solution {public:
	typedef priority_queue, vector>, greater<>> HTYPE;
	int minimumVisitedCells(vector>& grid) {m_r = grid.size();
		m_c = grid.front().size();
		vector> vDis(m_r, vector(m_c, -1));		
		vector< HTYPE> colMinHeaps(m_c);
		for (int r = 0; r < m_r; r++)
		{HTYPE rowMinHeap;
			auto Add = [&](const int r, const int c, int iNewDis)
			{vDis[r][c] = iNewDis;
				rowMinHeap.emplace(iNewDis, c + grid[r][c]);
				colMinHeaps[c].emplace(iNewDis, r + grid[r][c]);
			};
			for (int c = 0; c < m_c; c++)
			{if (r + c == 0)
				{Add(r, c, 1);
					continue;
				}
				while (rowMinHeap.size() && (rowMinHeap.top().second < c))
				{rowMinHeap.pop();
				}
				while (colMinHeaps[c].size() && (colMinHeaps[c].top().second < r ))
				{colMinHeaps[c].pop();
				}
				int iPreMin = INT_MAX;
				if (rowMinHeap.size())
				{iPreMin = min(iPreMin, rowMinHeap.top().first);
				}
				if (colMinHeaps[c].size())
				{iPreMin = min(iPreMin, colMinHeaps[c].top().first);
				}
				if (INT_MAX == iPreMin)
				{continue;
				}
				Add(r, c, iPreMin + 1);
			}
		}		
		return vDis.back().back();
	}
	int m_r, m_c;
};

单调向量（有序向量)

可以逆向考虑，从终点到起点。这样可以记录可以到达单元格的行（列）和经过的单格数。在保持数据的单调的情况下，行（列）递减，单格数递增。新增有利条件： 行（列）插入的顺序也递减。这意味者可以用单调向量。

代码

class Solution {public:
	int minimumVisitedCells(vector>& grid) {m_r = grid.size();
		m_c = grid.front().size();
		vector> vDis(m_r, vector(m_c, -1));
		vector< vector>> cols(m_c);//列（行）号按降序排除，距离按升序排列
		for (int r = m_r-1; r >= 0 ; r-- )
		{vector> row;
			auto Add = [&](const int r, const int c, int iNewDis)
			{vDis[r][c] = iNewDis;
				while (row.size() && (row.back().first >= iNewDis))
				{row.pop_back();
				}
				row.emplace_back(iNewDis,c);
				while (cols[c].size() && (cols[c].back().first >= iNewDis))
				{cols[c].pop_back();
				}
				cols[c].emplace_back(iNewDis, r);
			};
			auto Cmp = [&](const pair& pr, int rc)
			{return pr.second > rc;
			};
			for (int c = m_c-1 ; c >= 0 ;c--)
			{if (r + c + 2 == m_r+m_c )
				{Add(r, c, 1);
					continue;
				}				
				int iPreMin = INT_MAX;
				auto it = std::lower_bound(row.begin(), row.end(), c + grid[r][c], Cmp);
				if (row.end() != it )
				{iPreMin = min(iPreMin, it->first);
				}
				auto ij = std::lower_bound(cols[c].begin(), cols[c].end(), r + grid[r][c], Cmp);
				if (cols[c].end() != ij )
				{iPreMin = min(iPreMin, ij->first);
				}
				if (INT_MAX == iPreMin)
				{continue;
				}
				Add(r, c, iPreMin + 1);
			}
		}
		return vDis.front().front();
	}
	int m_r, m_c;
};

2023年8月版

typedef std::priority_queue,vector>,std::greater> > QUE;

class Solution {

public:

int minimumVisitedCells(vector& grid) {

m_r = grid.size();

m_c = grid[0].size();

vector 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(vector& grid) {

m_r = grid.size(), m_c = grid[0].size();

if (m_r * m_c == 1)

{

return 1;

}

vector>> vvRowMinDis(m_c); // 每列的单调栈

int iRet = m_iNotMay;

for (int r = m_r - 1; r >= 0; r–)

{

std::vector> 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::pair& 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::pair& 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;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。