Back to Leetcode

Readme

BFS/2577.Minimum-Time-to-Visit-a-Cell-In-a-Grid/Readme.md

latest1.3 KB
Original Source

2577.Minimum-Time-to-Visit-a-Cell-In-a-Grid

如果本题没有“you must move to any adjacent cell”这个要求,那么套用Dijkstra算法的模板即可求得到达右下角的最短路径。其中任意两条相邻的格子a->b之间的边权就是max(1, grid[b]-arrival[a],表示到达a之后,可以立即走一步到达b,或者原地等待到b的准入时刻再进入b。

以上算法的问题在于,我们不能在原地等待。假设我们到达a的时刻是3,但是其相邻的b点的准入时刻是5。显然,我们不能在时刻4的时候进入b,但我们可以再时刻5的时候进入b吗?其实也不能。我们唯一能拖延时间的方法就是从a走到一个相邻的格子再走回a,这样可以拖延两秒的时间,再进入b的时刻就是6. 同理我们可以发现,从a到任何与其相邻的格子b,考虑到“往复拖延”的策略,所需要的时间增量必然是+1,+3,+5,... 直至大于等于b的准入时刻。

所以我们只需要更新Dijkstra的部分代码。假设到达a的时刻是t,其相邻格子的准入时间是grid[b],那么如果grid[b]<=t+1,说明最早可以在t+1的时刻进入b;如果(grid[b]-t)%2==1,那么我们可以反复横跳之后恰好在grid[b]时刻进入b;否则我们需要在grid[b]+1时刻进入b。