UVa 1202 - Finding Nemo

// UVa 1202 - Finding Nemo

#include <iostream>
#include <string.h>
#include <limits.h>
#include <queue>
#include <cmath>
using namespace std;

struct pos {
	int x, y;
};

pos move[4] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

pos operator +(const pos & a, const pos & b) {
	return {a.x + b.x, a.y + b.y};
}

int lnk[201][201][4];
int T[201][201];
queue<pos> q, next_q;

int main() {
	int m, n;
	while (cin >> m >> n && m >= 0 && n >= 0) {
		// initialize
		memset(T, 127, sizeof(T));
		int oo = T[0][0];
		memset(lnk, 0, sizeof(lnk));
		// read walls
		for (; m; m--) {
			int x, y, d, t;
			cin >> x >> y >> d >> t;
			if (d)
				for (int yy = y; yy < y + t; yy++) {
					lnk[x][yy][2] = oo;
					lnk[x - 1][yy][0] = oo;
				}
			else
				for (int xx = x; xx < x + t; xx++) {
					lnk[xx][y][3] = oo;
					lnk[xx][y - 1][1] = oo;
				}
		}
		// read doors
		for (; n; n--) {
			int x, y, d;
			cin >> x >> y >> d;
			if (d) {
				lnk[x][y][2] = 1;
				lnk[x - 1][y][0] = 1;
			} else {
				lnk[x][y][3] = 1;
				lnk[x][y - 1][1] = 1;
			}
		}
		// read Nemo
		double nx, ny;
		cin >> nx >> ny;
		if (nx <= 0 || nx >= 200 || ny <= 0 || ny >= 200)
			cout << 0 << endl;
		else {
			pos nemo = { (int) (floor(nx)), (int) (floor(ny)) };
			// queue
			q = queue<pos>();
			next_q = queue<pos>();
			for (int x = 0; x <= 200; x++) {
				q.push( { x, 0 });
				T[x][0] = 0;
				q.push( { x, 200 });
				T[x][200] = 0;
			}
			for (int y = 1; y < 200; y++) {
				q.push( { 0, y });
				T[0][y] = 0;
				q.push( { 200, y });
				T[200][y] = 0;
			}
			// BFS
			for (int lvl = 0; !q.empty(); lvl++) {
				while (!q.empty()) {
					pos top = q.front();
					q.pop();
					for (int d = 0; d < 4; d++)
						if (lnk[top.x][top.y][d] != oo) {
							pos next = top + move[d];
							if (next.x > 0 && next.y > 0 && next.x < 200 && next.y < 200) {
								if (lnk[top.x][top.y][d] == 0 && T[next.x][next.y] > lvl) {
									T[next.x][next.y] = lvl;
									q.push(next);
								} else if (lnk[top.x][top.y][d] == 1 && T[next.x][next.y] == oo) {
									T[next.x][next.y] = lvl + 1;
									next_q.push(next);
								}
							}
						}
				}
				if (T[nemo.x][nemo.y] != oo)
					break;
				q = next_q;
				next_q = queue<pos>();
			}
			// print output
			if (T[nemo.x][nemo.y] != oo)
				cout << T[nemo.x][nemo.y] << endl;
			else
				cout << -1 << endl;
		}
	}
	return 0;
}