題意：在一個(gè)矩形平面內(nèi)，有若干道墻，現(xiàn)求從左部某一點(diǎn)到右部某一點(diǎn)的最短路徑。

解法：有一個(gè)事實(shí)是線(xiàn)路一定是從門(mén)兩邊的點(diǎn)上通過(guò)的，不可能出現(xiàn)從中間穿過(guò)的可能。因此我們就枚舉兩兩點(diǎn)之間是否可達(dá)，這里就要使用到線(xiàn)段相交的判定。構(gòu)好圖之后就是一個(gè)spfa搞定。

代碼如下：

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std;int N;struct Wall {double x, a, b, c, d; }w[20];struct Point {double x, y; }e[105]; int idx;struct Line {Point a, b;Line(Point x, Point y) {a = x, b = y;}friend bool cross(const Line &, const Line &); };double G[105][105];bool cross(const Line & Line1, const Line & Line2) {double Xa1 = Line1.a.x;double Ya1 = Line1.a.y;double Xa2 = Line1.b.x;double Ya2 = Line1.b.y;double Xb1 = Line2.a.x;double Yb1 = Line2.a.y;double Xb2 = Line2.b.x;double Yb2 = Line2.b.y;if(((Xa2-Xa1)*(Yb1-Ya1)-(Xb1-Xa1)*(Ya2-Ya1))*((Xa2-Xa1)*(Yb2-Ya1)-(Xb2-Xa1)*(Ya2-Ya1))>0)return false;if(((Xb2-Xb1)*(Ya1-Yb1)-(Xa1-Xb1)*(Yb2-Yb1))*((Xb2-Xb1)*(Ya2-Yb1)-(Xa2-Xb1)*(Yb2-Yb1))>0)return false;return true; }void insert(double x, double y) {e[idx].x = x, e[idx].y = y;++idx; }bool legal(int x, int y) {Line line = Line(e[x], e[y]);int l = (x-1)/4, r = (y-1)/4; // 分別計(jì)算出這些點(diǎn)屬于哪一面墻，再枚舉中間的墻if (x == 0) l = -1; // x==0時(shí)需特殊處理for (int i = l+1; i < r; ++i) { // 計(jì)算是否被墻擋住if (!cross(line, Line(e[i*4+1], e[i*4+2])) // 如果不從中間墻的某道門(mén)穿過(guò)的話(huà) && !cross(line, Line(e[i*4+3], e[i*4+4]))) {return false;}}return true; }double dist(const Point & a, const Point & b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }void build() {for (int i = 0; i < idx; ++i) {for (int j = i + 1; j < idx; ++j) { // 枚舉所有的兩兩組合 if (legal(i, j)) {G[i][j] = dist(e[i], e[j]);}}} }#include <queue> bool vis[105]; double dis[105]; void spfa() {memset(vis, 0, sizeof (vis));for (int i = 0; i < idx; ++i) {dis[i] = 10000000; }dis[0] = 0;queue<int>q;q.push(0);vis[0] = true;while (!q.empty()) {int v = q.front();q.pop();
vis[v] = false;for (int i = v+1; i < idx; ++i) {if (G[v][i] != 10000000 && dis[i] > dis[v] + G[v][i]) {dis[i] = dis[v] + G[v][i];if (!vis[i]) {vis[i] = true; q.push(i);}}} } }int main() {while (scanf("%d", &N), N != -1) {for (int i = 0; i < 105; ++i) {for (int j = 0; j < 105; ++j) {G[i][j] = 10000000; }}idx = 0;insert(0.0, 5.0);for (int i = 0; i < N; ++i) {scanf("%lf %lf %lf %lf %lf", &w[i].x, &w[i].a, &w[i].b, &w[i].c, &w[i].d);insert(w[i].x, w[i].a), insert(w[i].x, w[i].b);insert(w[i].x, w[i].c), insert(w[i].x, w[i].d);// 讀取所有的墻，并且添加四個(gè)點(diǎn) }insert(10, 5);build();spfa();printf("%.2f\n", dis[idx-1]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ-1556 The Doors 线段相交+最短路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。