Pagini recente » Cod sursa (job #299044) | Cod sursa (job #2100165) | Cod sursa (job #1944306) | Cod sursa (job #1107783) | Cod sursa (job #1647175)
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
class Point {
public:
int x, y;
};
Point rom, jul;
queue <Point> q;
int n, m, R_dist[105][105], J_dist[105][105];
int dir[8][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} };
bool mat[101][101];
char ch;
void bordare() {
for(int i = 0; i <= n+1; ++i) {
mat[i][0] = 1;
mat[i][m+1] = 1;
}
for(int j = 0; j <= m+1; ++j) {
mat[0][j] = 1;
mat[n+1][j] = 1;
}
}
void lee_R() {
///Initializare coada
q.push(rom);
R_dist[rom.x][rom.y] = 1;
while(!q.empty()) {
Point first = q.front();
q.pop();
for(int i = 0; i < 8; ++i) { ///Parcurgere directii
Point next;
next.x = first.x + dir[i][0];
next.y = first.y + dir[i][1];
if(mat[next.x][next.y]) { ///Obstacol
continue;
}
if(!R_dist[next.x][next.y]) { ///Nu a trecut pe aici (e clar ca pe unde trece prima oara o sa fie valoarea mai mica decat ar fi fost la alta trecere)
R_dist[next.x][next.y] = R_dist[first.x][first.y] + 1;
q.push(next);
}
}
}
}
void lee_J() {
///Initializare coada - o sa fie goala cand ajungi aici din cauza cond. de while din lee_R
q.push(jul);
J_dist[jul.x][jul.y] = 1;
while(!q.empty()) {
Point first = q.front();
q.pop();
for(int i = 0; i < 8; ++i) {
Point next;
next.x = first.x + dir[i][0];
next.y = first.y + dir[i][1];
if(mat[next.x][next.y]) { ///Obstacol
continue;
}
if(!J_dist[next.x][next.y]) { ///Nu a trecut pe aici
J_dist[next.x][next.y] = J_dist[first.x][first.y] + 1;
q.push(next);
}
}
}
}
int main() {
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
scanf("%d%d\n", &n, &m);
for(int i = 1; i <= n; ++i) {
char str[105];
gets(str);
int str_sz = strlen(str);
for(int j = 1; j <= str_sz; ++j) {
if(str[j - 1] == 'X') {
mat[i][j] = 1;
}
else if(str[j - 1] == 'R') {
rom.x = i;
rom.y = j;
}
else if(str[j - 1] == 'J') {
jul.x = i;
jul.y = j;
}
}
}
bordare();
///Puteam sa dau vectorul ca parametru dar am preferat sa fac 2 leeuri separate idk de ce
lee_R();
lee_J();
int ans = 0x3f3f3f3f; /// Un miliard si ceva... iti explic de ce am pus asa
Point ans_coord;
for(int i = 1; i <= n; ++i) {///Cea mai mica valoare a maximului dintre fiecare casuta din J_dist si R_dist va fi raspunsul
for(int j = 1; j <= m; ++j) {
int candidate = max(R_dist[i][j], J_dist[i][j]);
if(candidate and candidate < ans) {///Tb sa fie != 0 pentru a evita obstacolele
ans_coord.x = i;
ans_coord.y = j;
ans = candidate;
}
}
}
printf("%d %d %d\n", ans, ans_coord.x, ans_coord.y);///-1 pt ca am cons pozitia de plecare la distanta 1
return 0;
}