2013年8月1日

UVa 11049 - Basic wall maze

#include <cstdio>
#include <string>
#include <queue>
#include <set>
#include <map>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;
typedef pair<double, double> Pd;

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};
const string dir[4] = {"N", "E", "S", "W"};

int main() {
  int r1, c1, r2, c2;
  while (scanf("%d%d", &c1, &r1) && c1 || r1) {
    scanf("%d%d", &c2, &r2);
    set<Pd> block;
    for (int i = 0; i < 3; i++) {
      int sr, sc, er, ec;
      scanf("%d%d%d%d", &sc, &sr, &ec, &er);
      for (double r = sr + (sr == er ? 0.5 : 1); r <= er + (sr == er); r++) {
        for (double c = sc + (sc == ec ? 0.5 : 1); c <= ec + (sc == ec); c++) {
          block.insert(MP(r, c));
        }
      }
    }
    queue<P> q;
    map<P, string> path;
    P start = MP(r1, c1), end = MP(r2, c2);
    q.push(start);
    path[start] = ".";
    while (!q.empty()) {
      P now = q.front();
      double r = now.first, c = now.second;
      string p = path[now];
      q.pop();
      if (now == end) {
        puts(p.c_str() + 1);
        break;
      }
      for (int i = 0; i < 4; i++) {
        if (r + dr[i] > 0 && r + dr[i] <= 6 && c + dc[i] > 0 && c + dc[i] <= 6) {
          Pd pass = MP(r + dr[i] * 0.5, c + dc[i] * 0.5);
          P next = MP(r + dr[i], c + dc[i]);
          if (!block.count(pass) && !path.count(next)) {
            q.push(next);
            string newP = p + dir[i];
            path[next] = newP;
          }
        }
      }
    }
  }
  return 0;
}

沒有留言:

張貼留言