Pagini recente » Clasament ada27 | Cod sursa (job #1657056) | Istoria paginii utilizator/ileanamaria | Monitorul de evaluare | Cod sursa (job #1597445)
#include<fstream>
#include<queue>
#include<string.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int Di[8] = {1,-1,0,0,1,-1,1,-1};
int Dj[8] = {0,0,1,-1,1,1,-1,-1};
int Map_Romeo[110][110], N, M;
int Map_Julieta[110][110];
int pi, pj, ui, uj;
queue < pair < int, int > > C;
bool Check_R(int i, int j){
if(i<1 or i>N or j<1 or j>M)
return false;
if(Map_Romeo[i][j] == -1)
return false;
return true;
}
bool Check_J(int i, int j){
if(i<1 or i>N or j<1 or j>M)
return false;
if(Map_Julieta[i][j] == -1)
return false;
return true;
}
void Read(){
char s[110];
fin >> N >> M;
fin.getline(s,110);
for (int i=1; i<=N; ++i){
fin.getline(s,110);
for(int j=0; j<M; ++j){
if(s[j] == ' ')
Map_Romeo[i][j+1] = 0;
else if(s[j] == 'X')
Map_Romeo[i][j+1] = -1;
else if(s[j] == 'R'){
pi = i; pj = j+1;
Map_Romeo[i][j+1] = 1;
}
else if(s[j] == 'J'){
ui = i; uj = j+1;
Map_Romeo[i][j+1] = 0;
}
}
}
}
void Lee_Romeo(){
int i, j, Ni, Nj;
C.push(make_pair(pi, pj));
while(!C.empty() ){
i = C.front().first;
j = C.front().second;
C.pop();
for(int D=0; D<=7; ++D){
Ni = i + Di[D];
Nj = j + Dj[D];
if(Check_R(Ni, Nj) and Map_Romeo[Ni][Nj] == 0){
C.push(make_pair(Ni, Nj));
Map_Romeo[Ni][Nj] = Map_Romeo[i][j] + 1;
}
}
}
}
void Lee_Julieta(){
int i, j, Ni, Nj;
C.push(make_pair(ui, uj));
while(!C.empty() ){
i = C.front().first;
j = C.front().second;
C.pop();
for(int D=0; D<=7; ++D){
Ni = i + Di[D];
Nj = j + Dj[D];
if(Check_J(Ni, Nj) and Map_Julieta[Ni][Nj] == 0){
C.push(make_pair(Ni, Nj));
Map_Julieta[Ni][Nj] = Map_Julieta[i][j] + 1;
}
}
}
}
void Comp(){
int iC, jC, Min = 999999999;
for(int i=1; i<=N; ++i)
for(int j=1; j<=M; ++j){
if(Map_Julieta[i][j] < Min and Map_Julieta[i][j] == Map_Romeo[i][j] and Map_Romeo[i][j] > 0 and Map_Julieta[i][j] > 0){
iC = i; jC = j;
Min = Map_Julieta[iC][jC];
}
}
fout<<Map_Julieta[iC][jC]<<' '<<iC<<' '<<jC<<'\n';
}
int main(){
Read();
for(int i=1; i<=N; ++i)
for(int j=1; j<=M; ++j)
Map_Julieta[i][j] = Map_Romeo[i][j];
Map_Julieta[pi][pj] = 0;
Map_Julieta[ui][uj] = 1;
Lee_Romeo();
Lee_Julieta();
Comp();
}