那位大佬会c++。帮我做道题！

迪巴拉 · 发表于前天 20:25

马上注册，免费下载更多dz插件网资源。

您需要登录才可以下载或查看，没有账号？立即注册

×

抄近路描述琳琳每天要从家到车站，小区被道路分成许多正方形的块，共有N×M块，一般情况下，小区内的方块建有房屋，只能沿着附近的街道行走，有时方块表示公园，那么就可以直接穿过。
请你帮她计算一下从家到车站的最短距离。
输入第一行是N和M。注意，琳琳家坐标在方块(1,1)的西南角，车站在方块(M,N)的东北角。每个方块边长100米。接下来一行是整数K，表示可以对角线穿过的方块数，然后有K行，每行两个数，表示一个坐标。
输出输出最短距离，四舍五入到整数米。
样例输入3 231 13 21 2输出383提示0＜N,M≤1000

©DZ插件网所发布的一切资源仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。
本站内容为站长个人技术研究记录或网络，不提供用户交互功能，所有内容版权归原作者所有。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，得到更好的正版服务。
您在本站任何的赞助购买、下载、查阅、回复等行为等均表示接受并同意签订《DZ插件网免责声明协议》。
如有侵权请邮件与我们联系处理: discuzaddons@vip.qq.com 并出示相关证明以便删除。敬请谅解！

婷姐 · 发表于前天 20:26

#include <iostream>#include <vector>#include <queue>#include <cmath>#include <climits>#include <unordered_set>#include <utility>#include <iomanip>using namespace std;struct Point { int x, y; Point(int x_, int y_) : x(x_), y(y_) {} bool operator==(const Point& other) const { return x == other.x && y == other.y; }};namespace std { template<> struct hash<Point> { size_t operator()(const Point& p) const { return p.x * 1000 + p.y; } };}double calculateDistance(int x1, int y1, int x2, int y2, bool isPark) { if (isPark) { return sqrt(pow((x2 - x1) * 100, 2) + pow((y2 - y1) * 100, 2)); } else { return abs(x2 - x1) * 100 + abs(y2 - y1) * 100; }}double shortestPath(int N, int M, const unordered_set<Point>& parks) { vector<vector<double>> dist(M + 1, vector<double>(N + 1, INT_MAX)); dist[1][1] = 0; priority_queue<pair<double, Point>, vector<pair<double, Point>>, greater<pair<double, Point>>> pq; pq.push({0, Point(1, 1)}); int dx4[] = {-1, 1, 0, 0}; int dy4[] = {0, 0, -1, 1}; int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1}; while (!pq.empty()) { auto current = pq.top(); pq.pop(); double currentDist = current.first; Point u = current.second; if (u.x == M && u.y == N) { return currentDist; } if (currentDist > dist[u.x][u.y]) { continue; } bool isPark = parks.find(u) != parks.end(); if (isPark) { for (int i = 0; i < 8; ++i) { int nx = u.x + dx8[i]; int ny = u.y + dy8[i]; if (nx >= 1 && nx <= M && ny >= 1 && ny <= N) { double newDist = currentDist + calculateDistance(u.x, u.y, nx, ny, true); if (newDist < dist[nx][ny]) { dist[nx][ny] = newDist; pq.push({newDist, Point(nx, ny)}); } } } } else { for (int i = 0; i < 4; ++i) { int nx = u.x + dx4[i]; int ny = u.y + dy4[i]; if (nx >= 1 && nx <= M && ny >= 1 && ny <= N) { double newDist = currentDist + calculateDistance(u.x, u.y, nx, ny, false); if (newDist < dist[nx][ny]) { dist[nx][ny] = newDist; pq.push({newDist, Point(nx, ny)}); } } } } } return dist[M][N];}int main() { int N, M; cin >> N >> M; int K; cin >> K; unordered_set<Point> parks; for (int i = 0; i < K; ++i) { int x, y; cin >> x >> y; parks.insert(Point(x, y)); } double distance = shortestPath(N, M, parks); cout << static_cast<int>(round(distance)) << endl; return 0;}

复制代码

拾光 · 发表于前天 20:26

优先队列（堆优化）

priority_queue<pair<int, Point>, vector<pair<int, Point>>, greater<pair<int, Point>>> pq;pq.push({0, start});while (!pq.empty()) { auto [dist, u] = pq.top(); pq.pop(); if (dist > distance[u.x][u.y]) continue; // 跳过已处理的节点 for (auto [v, w] : neighbors) { if (distance[v.x][v.y] > dist + w) { distance[v.x][v.y] = dist + w; pq.push({distance[v.x][v.y], v}); } }}

复制代码

邻接表代替邻接矩阵

vector<vector<pair<Point, int>>> adj(N * M); // 邻接表for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { for (auto [dx, dy] : directions) { int nx = i + dx, ny = j + dy; if (nx >= 0 && nx < N && ny >= 0 && ny < M) { adj[i * M + j].emplace_back(Point(nx, ny), weight); } } }}

复制代码

双向Dijkstra或A*算法

// 双向Dijkstraunordered_set<Point> visited_start, visited_end;queue<Point> q_start, q_end;q_start.push(start); q_end.push(end);while (!q_start.empty() && !q_end.empty()) { expand(q_start, visited_start, visited_end); // 检查是否相遇 expand(q_end, visited_end, visited_start);}

复制代码