题目
思路
- 首先，这是一个最短路问题
- 直接用朴素记忆化搜索或者bfs无法实现“反复横跳”这一功能（只有有两个点以上可以走，就可以走到任意一个有最小时间限制的点）
- 所以更换思维，用图论的方式思考
- 每个点到上下左右有一条特殊的边，边权值为max(1,(grid[xx][yy]−dist[x][y])/2∗2+1)max( 1 , ( grid[ xx ][ yy ] - dist[ x ][ y ] ) / 2 * 2 + 1 )max(1,(grid[xx][yy]−dist[x][y])/2∗2+1)，前者是一步的权值，后者是需要“反复横跳”才能走到的位置
- 用堆优化dijkstra方法，因为最大的grid元素不超过1e5，所以堆中的元素是有限的，走的步数也是有限的
- 当新的最短路径长度小于dist中对应点的大小，更新dist，然后入队
- 教训：最短路问题都可以通过优化建边的技巧来解决┭┮﹏┭┮
- 下面方法和题解的思路有一点不同，通过观察下标得到一个重要的结论：走到一个点的步数奇偶性和下标x+y的奇偶性相同
- 其实都是一个道理，展现出来的面不同
代码
ini
复制代码
class Solution { struct node { int x,y,ti; bool operator < (const node & t)const{ return ti > t.ti; } }; public: int minimumTime(vector<vector<int>>& grid) { if(grid[0][1] > 1 && grid[1][0] > 1) { return -1; } int n = grid.size(),m = grid[0].size(); int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0}; vector<vector<int>> dist(n,vector<int>(m,1e9)); dist[0][0] = 0; priority_queue<node> q;q.push({0,0,0}); while(1){ auto[x, y, d] = q.top(); q.pop(); if (x == n - 1 && y == m - 1) return d; for (int i = 0;i < 4;i ++) { int xx = x + dx[i],yy = y + dy[i]; if (0 <= xx && xx < n && 0 <= yy && yy < m) { int nd = max(d + 1, grid[xx][yy]); nd += (nd - xx - yy) % 2; if (nd < dist[xx][yy]) { dist[xx][yy] = nd; // 更新最短路 q.push({xx,yy,nd}); } } } } return dist[n-1][m-1]; } };
