A*

#include <list>
#include <algorithm>

class Astar
{
 struct Node;
 typedef std::list<Node>::iterator Iterator;

 std::list<Node> open, closed;
 int endx, endy;

 struct Node
 {
  int x, y;
  Iterator prev;
  int dist;
  Node(int a, int b, Iterator i, int dx) : x(a), y(b), prev(i), dist(dx) {}
 };
 struct SelNode
 {
  int x, y;
  SelNode(int a, int b) : x(a), y(b) {}
  bool operator()(const Node& n) const { return n.x == x && n.y == y; }
 };

 template <class Vm>
 struct Alt
 {
  int x, y;
  const Vm* vm;
  Alt(const Vm& m, int a, int b) : vm(&m), x(a), y(b) {}
  bool operator()(const Node& rhs, const Node& lhs) const
  {
   return rhs.dist + vm->distance(rhs.x,rhs.y, x,y)
      < lhs.dist + vm->distance(lhs.x,lhs.y, x,y);
  }
 };

 bool is_closed(int x, int y) const
 {
  return std::find_if(closed.begin(), closed.end(), SelNode(x,y)) != closed.end();
 }

 template <typename Vm>
 void extend_anode(Iterator prev, int x, int y, const Vm& m);

public:
 template <class Vm, typename Op>
 void search(const Vm& m, std::pair<int,int> beg, std::pair<int,int> end, Op op);
};

#include <tr1/tuple>
#include <tr1/functional>

template <class Vm, typename Op>
void Astar::search(const Vm& m, std::pair<int,int> beg, std::pair<int,int> end, Op op)
{
 open.clear();
 closed.clear();
 std::tr1::tie(endx, endy) = end;
 closed.push_back(Node(beg.first, beg.second, closed.end(), 0));
 for (Iterator i = closed.begin(); i->x != endx || i->y != endy; i = closed.begin())
 {
  m.foreach_adjacents(i->x, i->y,
    std::tr1::bind(&Astar::extend_anode<Vm>, this, i, _1, _2, _3));
  if (open.empty())
  {
   closed.pop_back();
   op(m, open, closed);
   return;
  }
  closed.splice(closed.begin(), open,
    std::min_element(open.begin(), open.end(), Alt<Vm>(m, endx, endy)));
 }
 Iterator rbeg = closed.begin();
 for (Iterator i = rbeg->prev; i != closed.end(); i = i->prev)
  closed.splice(closed.begin(), closed, i);
 open.splice(open.end(), closed, ++rbeg, closed.end());
 op(m, closed, open);
}

template <class Vm>
void Astar::extend_anode(Iterator prev, int x, int y, const Vm& m)
{
 if (!this->is_closed(x, y))
 {
  int dist = prev->dist + m.distance(x,y, prev->x,prev->y);
  Iterator i = std::find_if(open.begin(), open.end(), SelNode(x,y));
  if (i == open.end())
   open.push_back(Node(x, y, prev, dist));
  else if (dist < i->dist)
   i->prev = prev, i->dist = dist;
 }
}

///////////////////////////////////////////////////////////////////////////
#include <cstdlib>

class Matrix
{
 char const* data;
 const int width, height;

 bool is_passable(int x, int y) const { return data[x + width * y] != '#'; }

public:
 explicit Matrix(const char* dat, int len, int w)
  : data(dat), width(w), height(len / w)
 {}

 int distance(int x, int y, int xx, int yy) const
 {
  int a = std::abs(x - xx);
  int b = std::abs(y - yy);
  return 10 * std::abs(a - b) + 14 * std::min(a, b);
 }

 template <typename Op>
 void foreach_adjacents(int xx, int yy, Op op) const
 {
  static int offx[] = {-1, 0,1,-1, /*0,*/ 1,-1, 0, 1};
  static int offy[] = { 1, 1,1, 0, /*0,*/ 0,-1,-1,-1};
  for (int i = 0; i < sizeof(offx) / sizeof(int); ++i)
  {
   int x = xx + offx[i], y = yy + offy[i];
   if (x >= 0 && x < width && y >= 0 && y < height && is_passable(x, y))
    op(x, y, *this);
  }
 }

 std::pair<int,int> begin() const
 {
  int ix = std::find(data, data + width*height-1, 'S') - data;
  return std::make_pair(ix % width, ix / width);
 }

 std::pair<int,int> end() const
 {
  int ix = std::find(data, data + width*height-1, 'E') - data;
  return std::make_pair(ix % width, ix / width);
 }

 template <typename R> void print(const R& r, const R& rr) const;
};

#include <iostream>
#include <iterator>

template <typename R>
void Matrix::print(const R& r, const R& rr) const
{
 using namespace std;
 string m(data, data + width*height);
 for (typename R::const_iterator i = r.begin(), ie = r.end(); i != ie; ++i)
  m[i->x + width * i->y] = '*';
 for (typename R::const_iterator i = rr.begin(), ie = rr.end(); i != ie; ++i)
  m[i->x + width * i->y] = ' ';
 if (!r.empty())
  m[r.front().x + width * r.front().y] = 'B',
  m[r.back().x + width * r.back().y] = 'E';
 for (int i = 0; i < height; ++i)
  copy(m.begin() + width*i, m.begin() + width*(i+1), ostream_iterator<char>(cout)),
  cout << endl;
}

struct Print
{
 template <typename R>
 void operator()(const Matrix& m, const R& r, const R& rr) const { m.print(r, rr); }
};

int main()
{
# define MATRIX_LINE \
 "############################################################"
# define MATRIX_DATA MATRIX_LINE \
 "#..........................................................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.......S.....................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#.............................#............................#" \
 "#######.#######################################............#" \
 "#....#........#............................................#" \
 "#....#........#............................................#" \
 "#....##########............................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "#...............................##############.............#" \
 "#...............................#........E...#.............#" \
 "#...............................#............#.............#" \
 "#...............................#............#.............#" \
 "#...............................#............#.............#" \
 "#...............................###########..#.............#" \
 "#..........................................................#" \
 "#..........................................................#" \
 "############################################################"
 Matrix mat1(MATRIX_DATA, sizeof(MATRIX_DATA)-1, sizeof(MATRIX_LINE)-1);
# undef MATRIX_LINE
# undef MATRIX_DATA

# define MATRIX_LINE \
 "###################"
# define MATRIX_DATA MATRIX_LINE \
 "#.................#" \
 "#........#........#" \
 "#........#........#" \
 "#..S.....#.....E..#" \
 "#........#........#" \
 "#........#........#" \
 "#.................#" \
 "###################"
 Matrix mat2(MATRIX_DATA, sizeof(MATRIX_DATA)-1, sizeof(MATRIX_LINE)-1);
# undef MATRIX_LINE
# undef MATRIX_DATA

 Astar astar;
 astar.search(mat1, mat1.begin(), mat1.end(), Print());
 astar.search(mat2, mat2.begin(), mat2.end(), Print());
}