# Untitled

unknown
plain_text
2 months ago
4.7 kB
0
Indexable
Never
```#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;
}
}
}
}```