2013年8月29日

UVa 589 - Pushing Boxes

#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

struct State {
  State(P box, P now, int push, string path) : box(box), now(now), push(push), path(path) {}
  bool operator<(const State & other) const {
    if (push != other.push) {
      return push > other.push;
    }
    return path.length() > other.path.length();
  }
  P box, now;
  int push;
  string path;
};

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};
const string d1[4] = {"s", "e", "n", "w"};
const string d2[4] = {"S", "E", "N", "W"};

int R, C;
char maze[22][22];

inline bool check(int r, int c) {
  return (r >= 0) && (r < R) && (c >= 0) && (c < C) && (maze[r][c] == '.');
}

bool vis[22][22][22][22][100];

void BFS(const State & init, const P & target) {
  memset(vis, false, sizeof(vis));
  vis[init.box.first][init.box.second][init.now.first][init.now.second][0] = true;

  priority_queue<State> q;
  q.push(init);

  int minPush = 1e9;
  string ans;
  while (!q.empty()) {
    State state = q.top();
    P box = state.box, now = state.now;
    int push = state.push;
    string path = state.path;
    q.pop();
    if (box == target) {
      if (push < minPush) {
        minPush = push;
        ans = path;
      } else if (push == minPush) {
        if (path.length() < ans.length()) {
          ans = path;
        }
      } else {
        break;
      }
      continue;
    }
    int br = box.first, bc = box.second;
    int r = now.first, c = now.second;
    for (int d = 0; d < 4; d++) {
      int nr = r + dr[d], nc = c + dc[d];
      if (!check(nr, nc)) {
        continue;
      }
      if (nr == br && nc == bc) {
        int nbr = br + dr[d], nbc = bc + dc[d];
        if (check(nbr, nbc)) {
          if (!vis[nbr][nbc][nr][nc][ans.length() + 1]) {
            vis[nbr][nbc][nr][nc][ans.length() + 1] = true;
            q.push(State(MP(nbr, nbc), MP(nr, nc), push + 1, path + d2[d]));
          }
        }
      } else {
        if (!vis[br][bc][nr][nc][ans.length() + 1]) {
          vis[br][bc][nr][nc][ans.length() + 1] = true;
          q.push(State(box, MP(nr, nc), push, path + d1[d]));
        }
      }
    }
  }
  puts(ans.length() ? ans.c_str() : "Impossible.");
}

int main() {
  int Case = 1;
  while (scanf("%d%d", &R, &C) && R) {
    P b, s, t;
    for (int r = 0; r < R; r++) {
      scanf("%s", maze[r]);
      for (int c = 0; maze[r][c]; c++) {
        if (maze[r][c] == 'B') {
          maze[r][c] = '.';
          b = MP(r, c);
        } else if (maze[r][c] == 'S') {
          maze[r][c] = '.';
          s = MP(r, c);
        } else if (maze[r][c] == 'T') {
          maze[r][c] = '.';
          t = MP(r, c);
        }
      }
    }
    printf("Maze #%d\n", Case++);
    BFS(State(b, s, 0, ""), t);
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言