## 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;
}
```