Untitled

#include <iostream>
using namespace std;

int n, m;
int dx, dy;
int arr[3001][3001];
int dd[3001][3001];
int dem[3001][3001];
int dR[4] = { -1, 0, 1, 0 };
int dC[4] = { 0, 1, 0, -1 };

typedef struct {
	int x, y;
}Point;

typedef struct {
	int front, rear;
	Point data[1000001];
}Queue;

void init(Queue& Q) {
	Q.front = Q.rear = -1;
}

void push(Queue& Q, Point value) {
	Q.rear++;
	Q.data[Q.rear] = value;
}

Point top(Queue& Q) {
	Point temp;
	Q.front++;
	temp = Q.data[Q.front];
	Q.front--;
	return temp;
}

void pop(Queue& Q) {
	Q.front++;
}

bool empty(Queue& Q) {
	if (Q.front == Q.rear)
		return true;
	return false;
}

Queue Q;

void BFS(Point P) {

	init(Q);
	push(Q, P);
	dd[P.x][P.y] = 1;
	dem[P.x][P.y] = 1;

	while (!empty(Q)) {
		Point P1 = top(Q);
		pop(Q);

		for (int k = 0; k < 4; k++) {
			int x = P1.x + dR[k];
			int y = P1.y + dC[k];

			if (x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] == 1 && dd[x][y] == 0) {
				dd[x][y] = 1;
				dem[x][y] = dem[P1.x][P1.y] + 1;

				Point P2;
				P2.x = x;
				P2.y = y;

				push(Q, P2);
			}
		}
	}

}

int main() {

	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {

		cin >> n >> m;
		cin >> dx >> dy;

		int x = -1, y = -1;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> arr[i][j];
				if (arr[i][j] == 2 && x == -1) {
					x = i;
					y = j;
				}
			}
		}

		Point P;
		P.x = dx;
		P.y = dy;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				dd[i][j] = 0;
				dem[i][j] = 0;
			}
		}

		BFS(P);

		/*cout << endl;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << dem[i][j] << " ";
			}
			cout << endl;
		}*/

		int count = 0;
		int count1 = -1;
		int count2 = -1;

		for (int k = 0; k < 4; k++) {
			int x1 = x + dR[k];
			int y1 = y + dC[k];

			if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && dd[x1][y1] == 1) {
				count++;
				count1 = max(count1, dem[x1][y1]);
			}
		}
		cout << "Case #" << tc << endl;
		if (count == 4) {
			cout << count1 << " ";
		}
		else {
			cout << "-1" << " ";
		}

		bool flag = true;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (dd[i][j] == 0 && arr[i][j] == 1) {
					flag = false;
					i = n + 1;
					break;
				}
				else if (arr[i][j] == 1 && dd[i][j] == 1) {
					count2 = max(count2, dem[i][j]);
				}
			}
		}

		if (!flag) {
			cout << "-1" << endl;
		}
		else {
			cout << count2 << endl;
		}
	}
	return 0;
}

#include <iostream>
#include <fstream>
using namespace std;

char arr[301][301];
int n, m;
int xe, ye;
int dR[4] = {-1, 0, 1, 0};
int dC[4] = {0, 1, 0, -1};
int dd[301][301];
int dem[301][301];

typedef struct {
	int x, y;
}Point;

typedef struct {
	int front, rear;
	Point data[100001];
}Queue;

void init(Queue& Q) {
	Q.front = Q.rear = -1;
}

void push(Queue& Q, Point value) {
	Q.rear++;
	Q.data[Q.rear] = value;
}

Point top(Queue& Q) {
	Point temp;
	Q.front++;
	temp = Q.data[Q.front];
	Q.front--;
	return temp;
}

void pop(Queue& Q) {
	Q.front++;
}

bool empty(Queue &Q) {
	if (Q.front == Q.rear)
		return true;
	return false;
}

Queue Q;

void BFS(Point P) {

	init(Q);
	push(Q, P);

	dd[P.x][P.y] = 1;
	dem[P.x][P.y] = 0;

	while (!empty(Q)) {

		Point P1;
		P1 = top(Q);
		pop(Q);

		for (int k = 0; k < 4; k++) {
			int x = P1.x + dR[k];
			int y = P1.y + dC[k];

			if (x >= 0 && x < n && y >= 0 && y < m
				&& arr[x][y] != 'S' && arr[x][y] != 'R' && dd[x][y] == 0) {
				dd[x][y] = 1;

				if (arr[x][y] == 'B')
					dem[x][y] = dem[P1.x][P1.y] + 2;
				else if(arr[x][y] == 'E' || arr[x][y] == 'T')
					dem[x][y] = dem[P1.x][P1.y] + 1;
				if (x == xe && y == ye)
					return;

				Point P2;
				P2.x = x;
				P2.y = y;

				push(Q, P2);
			}
		}
	}
}

int main() {

	ifstream input("input.txt");
	fstream output;
	output.open("output.txt");

	int t;
	input >> t;
	for (int tc = 1; tc <= t; tc++) {

		input >> n >> m;

		int xb = -1, yb = -1;
		xe = -1, ye = -1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				input >> arr[i][j];
				if (arr[i][j] == 'Y' && xb == -1) {
					xb = i;
					yb = j;
				}
				if (arr[i][j] == 'T' && xe == -1) {
					xe = i;
					ye = j;
				}
			}
		}

		/*cout << "Begin: " << xb << " " << yb << endl;
		cout << "End: " << xe << " " << ye << endl;*/

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				dd[i][j] = 0;
				dem[i][j] = 0;
			}
		}

		Point P;
		P.x = xb;
		P.y = yb;

		BFS(P);

		/*for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << dem[i][j] << " ";
			}
			cout << endl;
		}*/

		if (xe >= 0 && xe < n && ye >= 0 && ye < m) {
			if (dd[xe][ye] == 1) {
				output << dem[xe][ye] << endl;
			}
			else {
				output << "-1" << endl;
			}
		}
	}
}