人材獲得作戦の試験問題

http://okajima.air-nifty.com/b/2010/01/post-abc6.html
なんか流行ってるからやってみた。ただの幅優先探索。30分弱。vectorにするのさぼって配列使うために適当に100x100以下と仮定。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
class Maze {
    vector<string> maze;
    int W;
    int H;
    bool visited[100][100];
    int prev[100][100][2];
public:
    pair<int,int> findStart() {
        for (int y = 0; y < H; ++ y) {
            for (int x = 0; x < W; ++ x) {
                if (maze[y][x] == 'S') return make_pair(x, y);
            }
        }
        throw 1;
    }
    pair<int,int> func() {
        queue< pair<int,int> > Q;
        pair<int,int> start = findStart();
        Q.push(start);
        visited[start.second][start.first] = true;
        memset(visited, 0, sizeof(visited));
        memset(prev, -1, sizeof(prev));
        int dx[4] = {+1,-1, 0, 0};
        int dy[4] = { 0, 0,+1,-1};
        while (!Q.empty()) {
            pair<int,int> p = Q.front();
            Q.pop();
            for (int i = 0; i < 4; ++ i) {
                int x = p.first+dx[i];
                int y = p.second+dy[i];
                if (!visited[y][x] && maze[y][x] != '*') {
                    prev[y][x][0] = p.first;
                    prev[y][x][1] = p.second;
                    if (maze[y][x] == 'G') {
                        return make_pair(x, y);
                    } else {
                        Q.push(make_pair(x, y));
                        visited[y][x] = true;
                    }
                }
            }
        }
        throw 1;
    }
    vector<string> solve(const vector<string>& m) {
        maze = m;
        W = (int)maze[0].length();
        H = (int)maze.size();
        pair<int,int> p = func();
        for (;;) {
            p = make_pair(prev[p.second][p.first][0], prev[p.second][p.first][1]);
            if (maze[p.second][p.first] != ' ') break;
            maze[p.second][p.first] = '$';
        }
        return maze;
    }
};
int main() {
    char buf[1000];
    vector<string> hoge;
    while (cin.getline(buf, sizeof(buf))) {
        hoge.push_back(buf);
    }
    static Maze m;
    vector<string> r = m.solve(hoge);
    for (int i = 0; i < (int)r.size(); ++ i) {
        cout << r[i] << endl;
    }
}