人材獲得作戦の試験問題
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; } }