POJ 1475 - Pushing Boxes

http://poj.org/problem?id=1475

概要

r * c の二次元の迷路にスタート位置と箱の位置とゴールの位置が設定されている．

箱をゴールまで押して移動させたときの，最短のステップを答える． ただし，移動させることができないときは「Impossible」と出力する．

制約

解法

箱について BFS しつつ，1マス分動かす度に人を BFS で移動させる．

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 struct state
  7 {
  8   int man, box;
  9   string path;
 10   state(int m, int b, const string& p) : man(m), box(b), path(p) {}
 11 };
 12 
 13 struct in_range
 14 {
 15   int lower, upper;
 16   in_range(int l, int u) : lower(l), upper(u) {}
 17   bool operator()(int x) const { return lower <= x && x < upper; }
 18 };
 19 
 20 bool bfs(const vector<string>& maze, int start, int goal, int box, string& path)
 21 {
 22   const int R = maze.size();
 23   const int C = maze[0].size();
 24   const in_range r(0, R), c(0, C);
 25 
 26   queue<pair<string, int> > q;
 27   q.push(make_pair("", start));
 28   vector<vector<bool> > visited(R, vector<bool>(C, false));
 29   visited[start/C][start%C] = true;
 30   while (!q.empty()) {
 31     const pair<string, int> p = q.front();
 32     q.pop();
 33     if (p.second == goal) {
 34       path = p.first;
 35       return true;
 36     }
 37     for (int d = 0; d < 4; d++) {
 38       static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
 39       const int i = (p.second / C) + di[d];
 40       const int j = (p.second % C) + dj[d];
 41       if (r(i) && c(j) && i*C+j != box && maze[i][j] != '#' && !visited[i][j]) {
 42         static const char tbl[] = "nswe";
 43         visited[i][j] = true;
 44         q.push(make_pair(p.first + tbl[d], i*C+j));
 45       }
 46     }
 47   }
 48   return false;
 49 }
 50 
 51 string solve(const vector<string>& maze, int start, int goal, int box)
 52 {
 53   const int R = maze.size();
 54   const int C = maze[0].size();
 55   const in_range r(0, R), c(0, C);
 56 
 57   queue<state> q;
 58   q.push(state(start, box, ""));
 59   vector<vector<bool> > visited(R, vector<bool>(C, false));
 60   visited[box/C][box%C] = true;
 61   while (!q.empty()) {
 62     const state s = q.front();
 63     q.pop();
 64     if (s.box == goal) {
 65       return s.path;
 66     }
 67     for (int d = 0; d < 4; d++) {
 68       static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
 69       const int i = (s.box / C) + di[d];
 70       const int j = (s.box % C) + dj[d];
 71       const int k = (s.box / C) - di[d];
 72       const int l = (s.box % C) - dj[d];
 73       if (r(i) && c(j) && r(k) && c(l) && maze[i][j] != '#' && maze[k][l] != '#' && !visited[i][j]) {
 74         string path;
 75         if (bfs(maze, s.man, k*C+l, s.box, path)) {
 76           visited[i][j] = true;
 77           static const char tbl[] = "NSWE";
 78           q.push(state(s.box, i*C+j, s.path + path + tbl[d]));
 79         }
 80       }
 81     }
 82   }
 83   return "Impossible.";
 84 }
 85 
 86 int main()
 87 {
 88   for (int r, c, T = 1; cin >> r >> c && r != 0; ++T) {
 89     vector<string> maze(r);
 90     int start, goal, box;
 91     for (int i = 0; i < r; i++) {
 92       cin >> maze[i];
 93       for (int j = 0; j < c; j++) {
 94         if (maze[i][j] == 'S') {
 95           start = i*c + j;
 96           maze[i][j] = '.';
 97         } else if (maze[i][j] == 'T') {
 98           goal = i*c + j;
 99           maze[i][j] = '.';
100         } else if (maze[i][j] == 'B') {
101           box = i*c + j;
102           maze[i][j] = '.';
103         }
104       }
105     }
106     cout << "Maze #" << T << endl;
107     cout << solve(maze, start, goal, box) << endl;
108     cout << endl;
109   }
110   return 0;
111 }
poj/1475.cc