Untitled

#include <iostream>
using namespace std;

#define MAX_SIZE 10000000
int Arx[MAX_SIZE];
int Ary[MAX_SIZE];
int Cnt[MAX_SIZE];
int Trangthai[MAX_SIZE];
int front = -1, rear = -1;

int N, M;

int xbgin, ybgin, xend, yend;

class queue {
public:
	bool isEmpty();
	void enqueue(int arx, int ary, int cnt, int trangthai);
	void dequeue();
	void peek(int& arx, int& ary, int& cnt, int &trangthai);
};

bool queue::isEmpty()
{
	if (front == rear)
	{
		return true;
	}
	return false;
}

void queue::enqueue(int arx, int ary, int cnt, int trangthai)
{
	front++;
	Arx[front] = arx;
	Ary[front] = ary;
	Cnt[front] = cnt;
	Trangthai[front] = trangthai;

}

void queue::dequeue()
{
	rear++;
}

void queue::peek(int& arx, int& ary, int& cnt, int &trangthai)
{
	arx = Arx[rear + 1];
	ary = Ary[rear + 1];
	cnt = Cnt[rear + 1];
	trangthai = Trangthai[rear + 1];
}

char arr[201][201];
int ard[201][201];

void reset(char ar[201][201])
{
	for (int i = 0; i < 201; i++)
	{
		for (int j = 0; j < 201; j++)
		{
			ar[i][j] = 0;
			ard[i][j] = 0;
		}
	}
}

int dx[] = { -1, 0,  0,  1 };
int dy[] = { 0, 1, -1,  0 };


void  BFS(int x1, int y1, int x2,int y2)
{
	int th;
	int cnt = 1; // dung de dem so lan quay dau
	if (x1 == x2)
	{
		th = 1;
	}
	else 
	{
		th = 0;
	}
	queue qe;
	qe.enqueue(x1, y1, cnt, th);
	ard[x2][y2] = cnt;
	ard[x1][y1] = cnt;
	while (!qe.isEmpty())
	{
		int x, y;
		qe.peek(x, y, cnt , th);
		qe.dequeue();
		for (int i = 0; i < 4; i++)
		{
			int t = x + dx[i];
			int k = y + dy[i];
			if (t >= 0 && t < N && k >= 0 && k < M)
			{
				// trang thai tai phan tu t , k
				int th1;
				if (t == x)
				{
					th1 = 1;
				}
				else
				{
					th1 = 0;
				}
				int cnt2;
				// neu trang thai khac nhau cnt++
				if (th != th1)
				{
				    cnt2 = cnt + 1;
				}
				else
				{
					cnt2 = cnt;
				}

				if (ard[t][k] == 0 && arr[t][k] == '0')
				{
					qe.enqueue(t, k, cnt2, th1);
					ard[t][k] = cnt2;
				}
				else if(arr[t][k] == '0')
				{
					if (cnt < ard[t][k])
					{
						qe.enqueue(t, k, cnt2, th1);
						ard[t][k] = cnt2;
					}
				}
			}
		}
	}

}

int main()
{
	int testcase;
	cin >> testcase;
	for (int tc = 1; tc <= testcase; tc++)
	{
		cin >> M >> N;
		reset(arr);
		cin >> ybgin >> xbgin >> yend >> xend;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin >> arr[i][j];
			}
		}
		for (int i1 = 0; i1 < 4; i1++)
		{
			
			int x = xbgin - 1 + dx[i1];
			int y = ybgin - 1 + dy[i1];
			if (arr[x][y] == '0')
			{
				BFS(x, y, xbgin - 1, ybgin - 1);
			}
		}

		cout << "#" << tc << " " << ard[xend -1][yend -1] - 1 << endl;
	}
}