Untitled

#include <iostream>
using namespace std;

int T, n, m, xst, yst, xen, yen, map[500][500], visit[500][500];
int tmpx, tmpy, tx, ty, front, rear, qx[50000], qy[50000], dir[500][500];
int possible, minRotate;
void resetVisit() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			visit[i][j] = 0;
			dir[i][j] = 0;
		}
	}
}

void initQueue() {
	front = rear = -1;
}
int isEmpty() {
	return front == rear;
}
void enQueue(int x, int y) {
	qx[++rear] = x;
	qy[rear] = y;
}
void deQueue(int& tmpx, int& tmpy) {
	tmpx = qx[++front];
	tmpy = qy[front];
}

int isValid() {
	return tx > 0 && tx <= n && ty > 0 && ty <= m && map[tx][ty] == 0;
}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
void BFS(int x, int y) {
	initQueue();
	resetVisit();
	dir[x][y] = -1;
	visit[x][y] = 1;
	enQueue(x, y);
	while (!isEmpty()) {
		deQueue(tmpx, tmpy);
		if (tmpx == xen && tmpy == yen) {
			possible = 1;
			minRotate = visit[tmpx][tmpy] < minRotate ? visit[tmpx][tmpy] : minRotate;
		}
		for (int k = 0; k < 4; k++) {
			tx = tmpx + dx[k];
			ty = tmpy + dy[k];
			if (isValid()) {
				int temp = dir[tmpx][tmpy];
				if (!visit[tx][ty]) {
					if (temp == k) {
						dir[tx][ty] = temp;
						visit[tx][ty] = visit[tmpx][tmpy];
						enQueue(tx, ty);
					}
					else {
						dir[tx][ty] = k;
						visit[tx][ty] = visit[tmpx][tmpy] + 1;
						enQueue(tx, ty);
					}
				}
				else 
				{
					if (temp == k) {
						if (visit[tmpx][tmpy] < visit[tx][ty]) {
							visit[tx][ty] = visit[tmpx][tmpy];
							dir[tx][ty] = temp;
							enQueue(tx, ty);
						}	
					} 
					else {
						if (visit[tmpx][tmpy] + 1 < visit[tx][ty]) {
							visit[tx][ty] = visit[tmpx][tmpy] + 1;
							dir[tx][ty] = k;
							enQueue(tx, ty);
						}
					}
				}
			}
		}
	}
}

int main() {
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> m >> n;
		cin >> yst >> xst >> yen >> xen;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				char c;
				cin >> c;
				if (c == '1')
					map[i][j] = 1;
				else
					map[i][j] = 0;
				dir[i][j] = 0;
			}
		}
		possible = 0;
		minRotate = 1000000;
		cout << "Case #" << tc << endl;
		BFS(xst, yst);
		if (possible)
			cout << minRotate - 2 << endl;
		else 
			cout << -1<< endl;
	}
	return 0;
}