Untitled

#include <iostream>
using namespace std;

#define MAX_SIZE 10000000
int rear = -1, front = -1;
int Arx[MAX_SIZE] = {0};
int Ary[MAX_SIZE] = {0};
int Index[MAX_SIZE] = {0};

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

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

void queue :: enqueue(int arx, int ary, int index)
{
	front++;
	Arx[front] = arx;
	Ary[front] = ary;
	Index[front] = index;
}

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

void queue :: peek(int &arx, int &ary, int &index)
{
	arx = Arx[rear + 1];
	ary = Ary[rear + 1];
	index = Index[rear + 1];
}

int arr[3001][3001];
int ar[3001][3001];
void reset()
{
	for(int i = 0; i < 3001; i++)
	{
		for(int j = 0; j < 3001; j++)
		{
			arr[i][j] = 0;
			ar[i][j] = 0;
		}
	}
}

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

bool check_C(int xend1, int yend1, int N, int M)
{
	for(int i = 0; i < 4; i++)
	{
		int t = xend1 + dx[i];
		int k = yend1 + dy[i];
		if(t >= 0 && t < N && k >= 0 && k < M)
		{
			if(ar[t][k] == 0)
			{
				return false;
			}
		}
		else
			return false;
	}
	return true;
}


int main()
{
	freopen("input.txt", "r+", stdin);
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		int N , M;
		cin >> N >> M;
		reset();
		front = rear = -1;
		int xbgin, ybgin;
		cin >> xbgin >> ybgin;
		xbgin = xbgin - 1;
		ybgin = ybgin - 1;
		int xend1, yend1;

		int time1 = 0, time2 = 0;

		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < M; j++)
			{
				cin >> arr[i][j];
				if(arr[i][j] == 2)
				{
					xend1 = i;
					yend1 = j;
				}
			}
		}
		int index = 1;
		queue qe;
		qe.enqueue(xbgin, ybgin, index);
		ar[xbgin][ybgin] = index;
		int dk = 0;
		while(!qe.isEmpty())
		{
			int x, y;
			qe.peek(x, y, index);
			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)
				{
					if(arr[t][k] == 1 && ar[t][k] == 0)
					{
						qe.enqueue(t , k, index + 1);
						ar[t][k] = index + 1;
						if(check_C(xend1, yend1, N, M) && dk == 0)
			            {
				            dk = 1;
				           time1 = index + 1;
			            }
					}
				}
			}
			if(time2 < index)
			{
				time2 = index;
			}
		}
		if(time1 == 0)
		{
			time1 = -1;
		}
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < M; j++)
			{
				if(ar[i][j] == 0 && arr[i][j] == 1 && i != xbgin && j != ybgin)
				{
					time2 = -1;
					i = N;
					break;
				}
			}
		}
		if(time1 == -1)
		{
			time2 = -1;
		}
		cout<<"Case #"<<tc<<endl;
		cout<<time1<<" "<<time2<<endl;
	}
}