AOJ 2085 Turn Left
Turn Left
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2085
問題概要
交差点の座標、どの交差点の間に道があるか与えられる。
道は垂直方向か水平方向である。
右折をしないで目的地へ向かうときの最短距離のルートで向かったときの、
最短ステップ数を求めよ。
解法
ダイクストラ
状態はどの場所にいてどの方向を向いているか。
ソース
#include<iostream> #include<vector> #include<map> #include<string> #include<queue> #include<cmath> #include<cstdlib> #define REP(i, b, n) for(int i = b; i<(int)n; i++) #define rep(i, n) REP(i, 0, n) using namespace std; enum{ N, E, S, W }; const int NODE = 1005; const int INF = 10000000; vector<int> edge[NODE]; class State{ public: int d, step, pos, cost; bool operator<(const State &s)const{ if(cost != s.cost)return cost >s.cost; return step > s.step; } }; int getD(pair<int, int> from, pair<int, int> to){ if(to.second > from.second)return N; if(to.first > from.first)return E; if(to.second < from.second)return S; return W; } bool canGo(int from, int to){ if(from == N){ if(to == S || to == E)return false; return true; } if(from == E){ if(to == W || to == S)return false; return true; } if(from == S){ if(to == N || to == W)return false; return true; } if(from == W){ if(to == E || to == N)return false; return true; } } pair<int, int> XY[NODE]; int visited[NODE][4]; int getCost(int from, int to){ return max(abs(XY[from].first - XY[to].first), abs(XY[from].second - XY[to].second)); } int BFS(int start, int goal){ rep(i, NODE){ rep(j, 4){ visited[i][j] = INF; } } priority_queue<State> Q; rep(i, 4){ Q.push((State){i, 1, start, 0}); visited[start][i] = 0; } while(!Q.empty()){ State now = Q.top(); Q.pop(); if(now.cost > visited[now.pos][now.d])continue; if(now.pos == goal)return now.step; rep(i, edge[now.pos].size()){ int to = edge[now.pos][i]; int nextd = getD(XY[now.pos], XY[to]); int nextCost = now.cost + getCost(now.pos, to); if(!canGo(now.d, nextd))continue; if(visited[to][nextd] < nextCost)continue; visited[to][nextd] = nextCost; Q.push((State){nextd, now.step+1, to, nextCost}); } } return -1; } int main(){ int node, e; while(cin >> node >> e){ if(node == 0 && e== 0)break; rep(i, NODE){ edge[i].clear(); XY[i] = make_pair(-1, -1); } map<string, int> M; int cnt = 1; rep(i, node){ string name; cin >> name; if(M[name] == 0){ M[name] = cnt; cnt++; } cin >> XY[M[name]-1].first >> XY[M[name]-1].second; } rep(i, e){ string from, to; cin >> from >> to; int f = M[from]-1, t = M[to]-1; edge[f].push_back(t); edge[t].push_back(f); } string src, dst; cin >> src >> dst; int res = BFS(M[src] - 1, M[dst]-1); if( res < 0)cout << "impossible" << endl; else cout <<res << endl; } }