AOJ : 2085 - Turn Left

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2085
m 個の交差点の名前と位置が与えられます.
さらに, この m 個の交差点のどれか二つを結ぶ通りが n 本あります.
「直進」と「左折」のみを使って移動するとき, 交差点 src から交差点 dst まで行くのに, 最小で何回交差点を通る必要があるかを答える問題です.
ただし, スタートからゴールまでの移動距離は, 最短距離である必要があります.

アルゴリズム

交差点をノード, 通りをエッジとみなして, グラフを生成します.
あとは, 次の状態をもたせるクラスを作成し, ダイクストラ法で解きます.

• 現在の交差点の名前
• 現在向いている方向
• 今までの移動距離
• 今までに交差点を通った回数

グラフ生成が面倒ですが, それを作りさえすれば, あとは普通のダイクストラ法で解けます.
グラフは, 自分が処理しやすいように作りましょう.

プログラム

import java.util.*;
import java.awt.Point;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    while(true){
      int n = sc.nextInt();
      int m = sc.nextInt();
      if(n == 0 && m == 0) break;

      //各交差点の座標を記憶するマップ
      HashMap<String,Point> pmap = new HashMap<String,Point>();
      for(int i=0;i<n;i++){
        String name = sc.next();
        Point p = new Point(sc.nextInt(),sc.nextInt());
        pmap.put(name,p);
      }

      //交差点の東西南北の方向に, 他のどの交差点がつながっているかを記憶するマップ
      HashMap<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>();
      for(String name : pmap.keySet()){
        ArrayList<String> zeroList = new ArrayList<String>();
        for(int i=0;i<4;i++) zeroList.add(null);
        map.put(name,zeroList);
      }
      for(int i=0;i<m;i++){
        String s = sc.next();
        String d = sc.next();
        Point sp = pmap.get(s);
        Point dp = pmap.get(d);

        //交差点 s の東に交差点 d がある
        if(dp.x - sp.x > 0){
          map.get(s).set(1,d);
          map.get(d).set(3,s);
        }
        //交差点 s の西に交差点 d がある
        else if(dp.x - sp.x < 0){
          map.get(s).set(3,d);
          map.get(d).set(1,s);
        }
        //交差点 s の北に交差点 d がある
        else if(dp.y - sp.y > 0){
          map.get(s).set(0,d);
          map.get(d).set(2,s);
        }
        //交差点 s の南に交差点 d がある
        else {
          map.get(s).set(2,d);
          map.get(d).set(0,s);
        }
      }

      String s = sc.next();
      String d = sc.next();

      PriorityQueue<State> open = new PriorityQueue<State>();
      HashSet<State> closed = new HashSet<State>();
      for(int i=0;i<4;i++){
        open.add(new State(s,i,0,1));
      }

      State ans = null;

      while(!open.isEmpty()){
        State st = open.poll();
        if(closed.contains(st)) continue;
        closed.add(st);

        if(st.name.equals(d)){
          ans = st;
          break;
        }

        //直進
        String next = map.get(st.name).get(st.d);
        if(next != null){
          int dist = (int)pmap.get(st.name).distance(pmap.get(next));
          open.add(new State(next,st.d,st.dist+dist,st.cost+1));
        }

        //左折
        int nd = (st.d + 3) % 4; //左折の方向
        next = map.get(st.name).get(nd);
        if(next != null){
          int dist = (int)pmap.get(st.name).distance(pmap.get(next));
          open.add(new State(next,nd,st.dist+dist,st.cost+1));
        }
      }

      System.out.println(ans == null ? "impossible" : ans.cost);
    }
  }
}

class State implements Comparable<State>{
  String name; //交差点名
  int d,dist,cost; //現在向いている方向,今まで歩いた距離,通った交差点の数

  State(String name,int d,int dist,int cost){
    this.name = name;
    this.d = d;
    this.dist = dist;
    this.cost = cost;
  }

  public int compareTo(State st){
    if(dist < st.dist) return -1;
    else if(dist > st.dist) return 1;
    return cost - st.cost;
  }

  public boolean equals(Object o){
    State st = (State)o;
    return name.equals(st.name) && d == st.d;
  }

  public int hashCode(){
    return name.hashCode() + d;
  }
}