终点检查移到出队时确保返回的是最短路径LintCode 炼码 - 更高效的学习体验class Solution { public: /** * param maze: the maze * param start: the start * param destination: the destination * return: the shortest distance for the ball to stop at the destination */ int shortestDistance(vectorvectorint maze, vectorint start, vectorint destination) { // write your code here int m maze.size(); if (m 0) { return 0; } int n maze[0].size(); if (n 0) { return 0; } // 越大的越小 priority_queuepairint, int, vectorpairint, int, greaterpairint, int que; unordered_mapint, int dist; int begin start[0] * n start[1]; que.push({0, begin}); dist[begin] 0; while (!que.empty()) { auto f que.top(); que.pop(); int x f.second / n; int y f.second % n; if (x destination[0] y destination[1]) { return f.first; } vectorpairint, int nodes get_next_nodes(maze, dist, x, y, m, n); for (auto node : nodes) { if (node.first/n destination[0] node.first%n destination[1]) { //return dist[f.second] node.second; } if (dist.find(node.first) dist.end() || dist[f.second] node.second dist[node.first]) { dist[node.first] dist[f.second] node.second; que.push({dist[node.first], node.first}); } } } return -1; } vectorvectorint direc{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; vectorpairint, int get_next_nodes(vectorvectorint maze, unordered_mapint, int dist, int x, int y, int m, int n) { int QIANG 1; vectorpairint, int result; for (auto d : direc) { int next_x x; int next_y y; bool next false; int count 0; while (next_x d[0] 0 next_y d[1] 0 next_x d[0] m next_y d[1] n maze[next_xd[0]][next_yd[1]] ! QIANG) { count; next_x next_x d[0]; next_y next_y d[1]; next true; } if (next) { int next_node next_x * n next_y; result.push_back(pairint, int(next_node, count)); } } return result; } };class Solution { public: int shortestDistance(vectorvectorint maze, vectorint start, vectorint destination) { vectorvectorint distance(maze.size(), vectorint(maze[0].size(), INT_MAX)); vectorvectorbool visited(maze.size(), vectorbool(maze[0].size())); distance[start[0]][start[1]] 0; dijkstra(maze, start, distance); return distance[destination[0]][destination[1]] INT_MAX ? -1 : distance[destination[0]][destination[1]]; } vectorint minDistance(vectorvectorint distance, vectorvectorbool visited) { vectorint min{-1,-1}; int min_val INT_MAX; for (int i 0; i distance.size(); i) { for (int j 0; j distance[0].size(); j) { if (!visited[i][j] distance[i][j] min_val) { min {i, j}; min_val distance[i][j]; } } } return min; } void dijkstra(vectorvectorint maze, vectorint start, vectorvectorint distance) { vectorvectorint dirs{{0,1},{0,-1},{-1,0},{1,0}}; auto cmp [](vectorint a, vectorint b){return a[2] b[2];}; priority_queuevectorint, vectorvectorint, decltype(cmp) que(cmp); que.push({start[0],start[1],0}); while (!que.empty()) { vectorint s que.top(); que.pop(); if(distance[s[0]][s[1]] s[2]) continue; for (vectorint dir: dirs) { int x s[0] dir[0]; int y s[1] dir[1]; int count 0; while (x 0 y 0 x maze.size() y maze[0].size() maze[x][y] 0) { x dir[0]; y dir[1]; count; } if (distance[s[0]][s[1]] count distance[x - dir[0]][y - dir[1]]) { distance[x - dir[0]][y - dir[1]] distance[s[0]][s[1]] count; que.push({x - dir[0], y - dir[1], distance[x - dir[0]][y - dir[1]]}); } } } } };链接LintCode 炼码class Solution { public: int shortestDistance(vectorvectorint maze, vectorint start, vectorint destination) { vectorvectorint distance(maze.size(), vectorint(maze[0].size(), INT_MAX)); distance[start[0]][start[1]] 0; vectorvectorint dirs{{0, 1} ,{0, -1}, {-1, 0}, {1, 0}}; queuevectorint que; que.push(start); while (!que.empty()) { vectorint s que.front(); que.pop(); for (vectorint dir: dirs) { int x s[0] dir[0]; int y s[1] dir[1]; int count 0; while (x 0 y 0 x maze.size() y maze[0].size() maze[x][y] 0) { x dir[0]; y dir[1]; count; } if (distance[s[0]][s[1]] count distance[x - dir[0]][y - dir[1]]) { distance[x - dir[0]][y - dir[1]] distance[s[0]][s[1]] count; que.push({x - dir[0], y - dir[1]}); } } } return distance[destination[0]][destination[1]] INT_MAX ? -1 : distance[destination[0]][destination[1]]; } };