http://okajima.air-nifty.com/b/2010/01/post-abc6.html

maze.cc

// http://okajima.air-nifty.com/b/2010/01/post-abc6.html

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <utility>
#include <climits>
using namespace std;

const int INF = INT_MAX / 2;

const int LEFT = 0;
const int UP = 1;
const int RIGHT = 2;
const int DOWN = 3;
const int START = 4;

int main(int argc, char const* argv[]) {
  vector<string> maze;
  string s;
  while (getline(cin, s)) {
    maze.push_back(s);
  }

  const int w = maze[0].length();
  const int h = maze.size();

  int sx, sy, gx, gy;
  int trace[h][w];
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      trace[i][j] = INF;

      if (maze[i][j] == 'S') {
        sx = i; sy = j;
      }
      else if (maze[i][j] == 'G') {
        gx = i; gy = j;
      }
    }
  }

  deque<pair<int, int> > que;
  que.push_back(make_pair(sx, sy));
  trace[sx][sy] = START;

  const int dx[] = {0, -1, 0, 1};
  const int dy[] = {-1, 0, 1, 0};

  while (!que.empty()) {
    int x = que.front().first;
    int y = que.front().second;
    que.pop_front();

    for (int i = 0; i < 4; ++i) {
      int xx = x + dx[i];
      int yy = y + dy[i];

      if (xx < 0 || xx >= h || yy < 0 || yy >= w) { continue; }
      if (maze[xx][yy] == '*') { continue; }
      if (trace[xx][yy] != INF) { continue; }

      if (xx == gx && yy == gy) {
        while (true) {
          int t = trace[x][y];
          if (t == START) { break; }
          maze[x][y] = '$';
          x -= dx[t];
          y -= dy[t];
        }

        for (int j = 0; j < h; ++j) {
          cout << maze[j] << endl;
        }
        return 0;
      }

      trace[xx][yy] = i;
      que.push_back(make_pair(xx, yy));
    }
  }

  return 0;
}