Pagini recente » Cod sursa (job #807232) | Cod sursa (job #2178539) | Cod sursa (job #3256151) | Cod sursa (job #270409) | Cod sursa (job #2336836)
#include <fstream>
#include <queue>
#include <limits.h>
#define MAX 105
#define INF INT_MAX
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct coord{
int x, y;
};
queue < coord > Q;
int di[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dj[] = {1, 1, 0, -1, -1, -1, 0, 1};
int R[MAX][MAX];
int J[MAX][MAX];
int A[MAX][MAX];
int n, m;
int ir, jr, ij, jj;
bool verif(int i, int j){
if (i < 1 || j < 1 || j > m || i > n){
return false;
}
return true;
}
void alee(){
Q.push({ir, jr});
while (!(Q.empty())){
int i = Q.front().x;
int j = Q.front().y;
Q.pop();
for (int k = 0; k < 8; k++){
int new_i = i + di[k];
int new_j = j + dj[k];
if (verif(new_i, new_j) && R[new_i][new_j] != -1 && R[new_i][new_j] > 0 && R[new_i][new_j] > R[i][j] + 1){
R[new_i][new_j] = R[i][j] + 1;
Q.push({new_i, new_j});
}
}
}
Q.push({ij, jj});
while (!(Q.empty())){
int i = Q.front().x;
int j = Q.front().y;
Q.pop();
for (int k = 0; k < 8; k++){
int new_i = i + di[k];
int new_j = j + dj[k];
if (verif(new_i, new_j) && J[new_i][new_j] != -1 && J[new_i][new_j] > 0 && J[new_i][new_j] > J[i][j] + 1){
J[new_i][new_j] = J[i][j] + 1;
Q.push({new_i, new_j});
}
}
}
}
int main(){
int rj = 0, ri = 0, mini = INF;
fin >> n;
fin >> m;
fin.get();
for (int i = 1; i <= n; i++){
char C[256];
fin.getline(C, 256);
for (int j = 0; C[j] != '\0'; j++){
if (C[j] == ' '){
A[i][j + 1] = INF;
R[i][j + 1] = INF;
J[i][j + 1] = INF;
}
else{
if (C[j] == 'X'){
A[i][j + 1] = -1;
R[i][j + 1] = -1;
J[i][j + 1] = -1;
}
else{
if (C[j] == 'R'){
A[i][j + 1] = INF;
R[i][j + 1] = INF;
J[i][j + 1] = INF;
ir = i;
jr = j + 1;
}
else{
A[i][j + 1] = INF;
R[i][j + 1] = INF;
J[i][j + 1] = INF;
ij = i;
jj = j + 1;
}
}
}
}
}
R[ir][jr] = 0;
J[ij][jj] = 0;
alee();
/*for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
fout << R[i][j] << " ";
}
fout << "\n";
}
fout << "\n";
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
fout << J[i][j] << " ";
}
fout << "\n";
}
return 0;*/
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (R[i][j] == J[i][j] && R[i][j] < mini && R[i][j] > 0){
mini = R[i][j];
ri = i;
rj = j;
}
}
}
fout << mini + 1 << " " << ri << " " << rj;
return 0;
}