#include #include #include #include #include using namespace std; #define MAXN 251001 #define INF 999666111 const char *infile = "harem.inp"; const char *outfile = "harem.out"; int ans; int reg[512][512]; int w_type = 1; bool w_inc; bool readoneint(FILE *f, int *a) { int x; char s[100]; int res = fscanf(f, "%s", s); if (res != 1) return false; x = 0; for (int i = 0; i < strlen(s); i++) { if (s[i] == '}') w_inc = true; if (s[i] >= '0' && s[i] <= '9') { x = x * 10 + s[i] - '0'; } } *a = x; return true; } bool read4ints(FILE *f, int a[]) { if (w_inc) w_type ++; w_inc = false; for (int i =0 ; i < 4; i++) { if (!readoneint(f, a+i)) return false; } return true; } void InX(void) { FILE *f = fopen(infile, "rt"); int x1, y1, x2, y2; char s[50*100]; /* while (read4ints(f, a)) { printf("filling region {%d, %d, %d, %d} with color %d\n", a[0], a[1], a[2], a[3], w_type); for (int i = a[0]; i <= a[2]; i++) for (int j = a[1]; j <= a[3]; j++) reg[i][j] = w_type; }*/ for (w_type = 1; w_type < 3; w_type++) { fgets(s, 50*100, f); int l = strlen(s); int i=0 , j; while (1) { while (i < l && s[i] != '"') i++; if (i >= l) break; int j = i + 1; while (j < l && s[j] != '"') j++; s[j]=0; sscanf(s+i+1, "%d %d %d %d", &x1,&y1, &x2, &y2); // printf("filling region {%d, %d, %d, %d} with color %d\n", x1, y1, x2, y2, w_type); for (int x = x1; x <= x2; x++) for (int y = y1; y <= y2; y++) reg[x][y] = w_type; i = j + 1; } } reg[0][0] = 0; fclose(f); } void OutX(void) { FILE *f = fopen(outfile, "wt"); fprintf(f, "%d\n", ans); fclose(f); } #define nd(xx,yy) ((xx)*501+(yy)) int dir[4][2]= { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; struct node { int dest, cost; node(){} node(int d, int c) { dest =d; cost = c; } bool operator < (const node & r) const { return cost > r.cost; } }; node g[MAXN][4]; int c[MAXN]; int target; void build_graph(void) { int x, y; for (int i = 0; i <= 500; i++) { for (int j = 0; j <= 500; j++) { for (int k = 0; k < 4; k++) { x = i + dir[k][0]; y = j + dir[k][1]; if (x >= 0 && x <= 500 && y >= 0 && y <= 500) { int org = nd(i,j); if (reg[x][y]< 2) { g[org][c[org]++] = node(nd(x, y), reg[x][y]); } } } } } } int ps[MAXN], ds[MAXN]; void dijkstra(int root) { for (int i = 0; i < MAXN; i++) { ps[i] = 0; ds[i] = INF; } ds[root] = 0; priority_queue q; q.push(node(root, 0)); while (!q.empty()) { while (!q.empty() && ps[q.top().dest]) { q.pop(); } if (q.empty()) break; node n = q.top(); q.pop(); int bi = n.dest; if (target == bi) break; ps[bi] =1; // printf("ps[%d] = true\n", bi); for (int i = 0; i < c[bi]; i++) { int j = g[bi][i].dest; int d = g[bi][i].cost + ds[bi]; if (!ps[j] && ds[j] > d) { ds[j] = d; q.push(node(j, d)); } } } } void DoWork(void) { build_graph(); target = nd(500,500); dijkstra(0); ans = ds[target]; if (ans >= INF) ans = -1; } int main(void) { InX(); DoWork(); OutX(); // system("pause"); return 0; }