Pagini recente » Cod sursa (job #2738433) | Cod sursa (job #6042) | Cod sursa (job #152159) | Cod sursa (job #1150865) | Cod sursa (job #1343878)
#include <iostream>
#include <fstream>
#include <queue>
#define nmax 105
#define inf -100000
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
char a[nmax][nmax];
int dist[2][nmax][nmax];
int n, m;
bool ok;
queue< pair<int, int> > q;
pair<int, int> romeo, juliet;
void create_second_matrix(){
for(int i=0; i<=n+1; i++)
for(int j=0; j<=m+1; j++)
if(a[i][j]== ' ' && i>0 && j>0 && i<n+1 && j<m+1) dist[0][i][j]= -1, dist[1][i][j]= -1;
else dist[0][i][j]= inf, dist[1][i][j]= inf;
dist[0][romeo.first][romeo.second]= 0;
dist[1][juliet.first][juliet.second]= 0;
dist[0][juliet.first][juliet.second]= -1;
dist[1][romeo.first][romeo.second]= -1;
}
void LEE(){
q.push(make_pair(romeo.first, romeo.second));
while(!q.empty()){
int i= q.front().first;
int j= q.front().second;
q.pop();
if(dist[0][i-1][j]==-1){
q.push(make_pair(i-1, j));
dist[0][i-1][j]= dist[0][i][j]+1;
}
if(dist[0][i][j+1]==-1){
q.push(make_pair(i, j+1));
dist[0][i][j+1]= dist[0][i][j]+1;
}
if(dist[0][i+1][j]==-1){
q.push(make_pair(i+1, j));
dist[0][i+1][j]= dist[0][i][j]+1;
}
if(dist[0][i][j-1]==-1){
q.push(make_pair(i, j-1));
dist[0][i][j-1]= dist[0][i][j]+1;
}
if(dist[0][i+1][j+1]==-1){
q.push(make_pair(i+1, j+1));
dist[0][i+1][j+1]= dist[0][i][j]+1;
}
if(dist[0][i-1][j-1]==-1){
q.push(make_pair(i-1, j-1));
dist[0][i-1][j-1]= dist[0][i][j]+1;
}
if(dist[0][i+1][j-1]==-1){
q.push(make_pair(i+1, j-1));
dist[0][i+1][j-1]= dist[0][i][j]+1;
}
if(dist[0][i-1][j+1]==-1){
q.push(make_pair(i-1, j+1));
dist[0][i-1][j+1]= dist[0][i][j]+1;
}
}
q.push(make_pair(juliet.first, juliet.second));
while(!q.empty()){
int i= q.front().first;
int j= q.front().second;
q.pop();
if(dist[1][i-1][j]==-1){
q.push(make_pair(i-1, j));
dist[1][i-1][j]= dist[1][i][j]+1;
}
if(dist[1][i][j+1]==-1){
q.push(make_pair(i, j+1));
dist[1][i][j+1]= dist[1][i][j]+1;
}
if(dist[1][i+1][j]==-1){
q.push(make_pair(i+1, j));
dist[1][i+1][j]= dist[1][i][j]+1;
}
if(dist[1][i][j-1]==-1){
q.push(make_pair(i, j-1));
dist[1][i][j-1]= dist[1][i][j]+1;
}
if(dist[1][i+1][j+1]==-1){
q.push(make_pair(i+1, j+1));
dist[1][i+1][j+1]= dist[1][i][j]+1;
}
if(dist[1][i-1][j-1]==-1){
q.push(make_pair(i-1, j-1));
dist[1][i-1][j-1]= dist[1][i][j]+1;
}
if(dist[1][i+1][j-1]==-1){
q.push(make_pair(i+1, j-1));
dist[1][i+1][j-1]= dist[1][i][j]+1;
}
if(dist[1][i-1][j+1]==-1){
q.push(make_pair(i-1, j+1));
dist[1][i-1][j+1]= dist[1][i][j]+1;
}
}
}
int main(){
string s;
fin.sync_with_stdio(false);
fin >> n >> m;
fin.get();
for(int i=1; i<=n; i++){
getline(fin, s);
for(int j=0; j<m; j++){
a[i][j+1]= s[j];
if(s[j]=='R') romeo.first= i, romeo.second= j+1;
if(s[j]=='J') juliet.first= i, juliet.second= j+1;
}
}
create_second_matrix();
LEE();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(dist[0][i][j]==dist[1][i][j] && dist[0][i][j]!= inf && dist[0][i][j]!= -1){
fout << dist[0][i][j]+1 << " " << i << " " << j << " ";
return 0;
}
return 0;
}