A*

http://okajima.air-nifty.com/b/2010/01/post-abc6.html
余計なことして遊んでたらマジで制限時間ギリギリの3時間かかってしまった．．．orz
しかも色々はしょっているわ，出力に S, G が出てないわ．．．
A* で discover されなかったノードに対する情報を出来る限りメモリに乗せないように (implicit graph っぽく) 作るにはどうするんでしょうねぇ，ということを試したかったので意味不明な書き方になってるんだけれど，まー，この入力で A* (@壁をぶち抜く heuristics) だと結局ノードを全部 discover しちゃってる (ホンマかそれ？) よね．．．
書いた結果の感想としては，こういう問題 (2次元の迷路) だと A* でやってもあんまり楽しくないので普通に BFS で距離埋めていけば良いのではないでしょうか的な． A* は，あれですよ，ほら．もっとこう本質的に高次元で2つ隣を列挙するのすらやばげな問題のほうが面白いと思う．知らんけど？
GCC 4.5 20100107 snapshot の -std=c++0x オプション付 + Boost 1.40.0 で動作確認っていうか，この C++0x をふんだんに取り入れた贅沢な一品を動かせる実装は恐らく GCC 4.5 以外にまだ無いはず．

#include <limits>
#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>

#include <boost/unordered_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/iterator_adaptor.hpp>



namespace Cry{

class G
{
private:
  enum struct N{
    space,
    wall,
    ans
  };

public:
  typedef int vertex_descriptor;
  typedef vertex_descriptor V;
  typedef std::pair<int, int> edge_descriptor;
  typedef edge_descriptor E;
  typedef boost::undirected_tag directed_category;
  typedef boost::disallow_parallel_edge_tag edge_parallel_category;
  struct traversal_category
    : boost::incidence_graph_tag,
      //boost::graph::adjacency_graph_tag,
      boost::vertex_list_graph_tag
  {};
  static V null_vertex(){ return std::numeric_limits<V>::max(); }

public:
  class out_edge_iterator
    : public boost::iterator_facade<
        out_edge_iterator,
        E,
        boost::forward_traversal_tag,
        E>
  {
    enum struct Dir{
      none,
      up,
      right,
      down,
      left,
      fin
    };

    friend class G;
    friend class boost::iterator_core_access;

    out_edge_iterator(G const &self, V v)
      : p_(&self),
	v_(v),
	d_(Dir::up)
    {
      skipImpl();
    }

  public:
    out_edge_iterator()
      : p_(),
	v_(null_vertex()),
	d_(Dir::fin)
    {}

    // Compiler-generated cctor, dtor and assignment are fine.

  private:
    E dereference() const {
      V x = 0;
      V y = 0;
      switch (d_) {
      case Dir::up:
	x = v_ / p_->width() - 1;
	y = v_ % p_->width();
	break;
      case Dir::right:
	x = v_ / p_->width();
	y = v_ % p_->width() + 1;
	break;
      case Dir::down:
	x = v_ / p_->width() + 1;
	y = v_ % p_->width();
	break;
      case Dir::left:
	x = v_ / p_->width();
	y = v_ % p_->width() - 1;
	break;
      default:
	throw 1;
	break;
      }
      return std::make_pair(v_, x * p_->width() + y);
    }

    void increment() {
      switch (d_) {
      case Dir::up:
	d_ = Dir::right;
	skipImpl();
	break;
      case Dir::right:
	d_ = Dir::down;
	skipImpl();
	break;
      case Dir::down:
	d_ = Dir::left;
	skipImpl();
	break;
      case Dir::left:
	d_ = Dir::fin;
	break;
      default:
	throw 1;
	break;
      }
    }

    bool equal(out_edge_iterator const &x) const {
      return d_ == x.d_;
    }

    void skipImpl() {
      switch (d_) {
      case Dir::up:
	if (v_ / p_->width() == 0) {
	  d_ = Dir::right;
	  skipImpl();
	}
	else if (p_->isWall(dereference().second)) {
	  d_ = Dir::right;
	  skipImpl();
	}
	break;
      case Dir::right:
	if (v_ % p_->width() == p_->width() - 1) {
	  d_ = Dir::down;
	  skipImpl();
	}
	else if (p_->isWall(dereference().second)) {
	  d_ = Dir::down;
	  skipImpl();
	}
	break;
      case Dir::down:
	if (v_ / p_->width() == p_->height() - 1) {
	  d_ = Dir::left;
	  skipImpl();
	}
	else if (p_->isWall(dereference().second)) {
	  d_ = Dir::left;
	  skipImpl();
	}
	break;
      case Dir::left:
	if (v_ % p_->width() == 0) {
	  d_ = Dir::fin;
	}
	else if (p_->isWall(dereference().second)) {
	  d_ = Dir::fin;
	}
	break;
      case Dir::fin:
	break;
      default:
	throw 1;
	break;
      }
    }

  private:
    G const *p_;
    V v_;
    Dir d_;
  };

  typedef std::size_t degree_size_type;

  class adjacency_iterator
    : public boost::iterator_adaptor<
        adjacency_iterator,
        out_edge_iterator,
        V,
        boost::forward_traversal_tag,
        V>
  {
    friend class G;
    friend class boost::iterator_core_access;

    adjacency_iterator(G const &g, V v)
      : iterator_adaptor_({g, v})
    {}

  public:
    adjacency_iterator()
      : iterator_adaptor_()
    {}

  private:
    V dereference() const {
      return base_reference()->second;
    }
  };

  class in_edge_iterator
    : public boost::iterator_adaptor<
        in_edge_iterator,
        out_edge_iterator,
        E,
        boost::forward_traversal_tag,
        E>
  {
    friend class G;
    friend class boost::iterator_core_access;

    in_edge_iterator(G const &g, V v)
      : iterator_adaptor_({g, v})
    {}

  public:
    in_edge_iterator()
      : iterator_adaptor_()
    {}

  private:
    E dereference() const {
      return E(base_reference()->second, base_reference()->first);
    }
  };

  class vertex_iterator
    : public boost::iterator_adaptor<
        vertex_iterator,
        int,
        V,
        boost::forward_traversal_tag,
        V,
        int>
  {
    friend class G;
    friend class boost::iterator_core_access;

    explicit vertex_iterator(G const &self)
      : iterator_adaptor_(0),
	p_(&self)
    {
      skipImpl();
    }

  public:
    vertex_iterator()
      : iterator_adaptor_(),
	p_()
    {}

  private:
    V dereference() const {
      return base_reference();
    }

    void increment() {
      ++base_reference();
      skipImpl();
    }

    bool equal(vertex_iterator const &x) const {
      if (!p_ && x.base_reference() == p_->width() * p_->height()) {
	return true;
      }
      if (base_reference() == p_->width() * p_->height() && !x.p_) {
	return true;
      }
      return base_reference() == x.base_reference();
    }

    void skipImpl() {
      while (base_reference() != p_->width() * p_->height()
	     && p_->isWall(base_reference())) {
	++base_reference();
      }
    }

  private:
    G const *p_;
  };

  typedef std::size_t vertices_size_type;

  class edge_iterator;

  typedef std::size_t edges_size_type;

public:
  explicit G(std::istream &is)
    : v_(),
      w_(),
      h_(),
      s_(),
      g_()
  {
    bool first_line = true;
    int x = 0;
    std::for_each(
      std::istreambuf_iterator<char>(is),
      std::istreambuf_iterator<char>(),
      [&](char c) -> void {
	switch (c) {
	case ' ':
	  v_.push_back(N::space);
	  ++x;
	  break;
	case '*':
	  v_.push_back(N::wall);
	  ++x;
	  break;
	case 'S':
	  v_.push_back(N::space);
	  s_ = x++;
	  break;
	case 'G':
	  v_.push_back(N::space);
	  g_ = x++;
	  break;
	case '\n':
	  if (first_line) {
	    w_ = x;
	    first_line = false;
	  }
	  break;
	default:
	  throw 1;
	}
      });
    h_ = x / w_;
    if (x % w_ != 0) {
      throw 1;
    }
  }

  int width() const{ return w_; }

  int height() const { return h_; }

  V start() const{ return s_; }

  V goal() const{ return g_; }

  bool isWall(V u) const { return v_[u] == N::wall; }

  friend V source(E e, G const &g) { return e.first; }

  friend V target(E e, G const &g) { return e.second; }

  std::pair<out_edge_iterator, out_edge_iterator> out_edges(V u) const
  { return { out_edge_iterator(*this, u), out_edge_iterator() }; }

  friend std::pair<out_edge_iterator, out_edge_iterator> out_edges(V u, G const &g)
  { return g.out_edges(u); }

  friend degree_size_type out_degree(V u, G const &g) {
    auto oe = g.out_edges(u);
    return std::distance(oe.first, oe.second);
  }

  std::pair<vertex_iterator, vertex_iterator> vertices() const
  { return { vertex_iterator(*this), vertex_iterator() }; }

  friend std::pair<vertex_iterator, vertex_iterator> vertices(G const &g)
  { return g.vertices(); }

  int getHeuristics(V u) const { int i = std::abs(u / w_ - g_ / w_) + std::abs(u % w_ - g_ % w_); return i; }

  void check(V u) { v_[u] = N::ans; }

  void print() {
    int x = 0;
    std::for_each(v_.begin(), v_.end(),
		  [&](N n) -> void {
		    switch (n) {
		    case N::wall:
		      std::cout << '*';
		      break;
		    case N::space:
		      std::cout << ' ';
		      break;
		    case N::ans:
		      std::cout << '$';
		      break;
		    default:
		      throw 1;
		      break;
		    }
		    ++x;
		    if (x == w_) {
		      std::cout << '\n';
		      x = 0;
		    }
		  });
  }

private:
  std::vector<N> v_;
  int w_;
  int h_;
  V s_;
  V g_;
};



template<class F, class K, class T>
class func_pmap{
  F f_;

public:
  typedef K key_type;
  typedef T value_type;
  typedef T &reference;
  typedef boost::read_write_property_map_tag category;

  explicit func_pmap(F f)
    : f_(f)
  {}

  friend T get(func_pmap p, K const &k)
  { return p.f_(k); }

  friend void put(func_pmap p, K const &k, T const &x)
  { p.f_(k) = x; }
};

template<class K, class T, class F>
func_pmap<F, K, T> make_func_pmap(F f)
{ return func_pmap<F, K, T>(f); }

}

class Val
{
  boost::tuple<Cry::G::V, int, int, boost::default_color_type> t_;

public:
  Val()
    : t_(Cry::G::null_vertex(),
	 std::numeric_limits<int>::max(),
	 std::numeric_limits<int>::max(),
	 boost::color_traits<boost::default_color_type>::white())
  {}

  Cry::G::V &predecessor() { return t_.get<0>(); }
  int &cost() { return t_.get<1>(); }
  int &dist() { return t_.get<2>(); }
  boost::default_color_type &color() { return t_.get<3>(); }
};

int main()
{
  Cry::G g(std::cin);
  Cry::G::V s = g.start();

  typedef boost::unordered_map<Cry::G::V, Val> M;
  M m;

  boost::astar_search_no_init(
    g,
    s,
    [&](Cry::G::V u) -> int { return g.getHeuristics(u); },
    boost::astar_visitor<boost::null_visitor>(),
    Cry::make_func_pmap<Cry::G::V, Cry::G::V>([&](Cry::G::V u) -> Cry::G::V & { return m[u].predecessor(); }), // predecessor
    Cry::make_func_pmap<Cry::G::V, int>([&](Cry::G::V u) -> int & { return m[u].cost(); }), // Cost
    Cry::make_func_pmap<Cry::G::V, int>([&](Cry::G::V u) -> int & { return m[u].dist(); }), // Dist
    Cry::make_func_pmap<Cry::G::E, int>([&](Cry::G::E /*e*/) -> int { return 1; }), // Weight
    Cry::make_func_pmap<Cry::G::V, boost::default_color_type>([&](Cry::G::V u) -> boost::default_color_type & { return m[u].color(); }), // Color
    Cry::make_func_pmap<Cry::G::V, int>([&](Cry::G::V v) -> int { return v; }), // Index
    std::less<int>(),
    std::plus<int>(),
    std::numeric_limits<int>::max(),
    0);

  Cry::G::V u = g.goal();
  while (u != s) {
    g.check(u);
    u = m[u].predecessor();
  }
  g.check(s);
  g.print();
}