Pagini recente » Cod sursa (job #2725091) | Cod sursa (job #301511) | Cod sursa (job #2668624)
#include <iostream>
#include <fstream>
#include<string>
#include<cstring>
#include <queue>
using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");
int n,m,x,y,Julieta[105][105],Romeo[105][105],minim = 99999999;
char linie[105];
struct coordonate
{
int x,y;
} romeo,julieta,intalnire;
int dx[]= {0, 0, 1, 0, -1, -1, 1, -1, 1};
int dy[]= {0, 1, 0, -1, 0, -1, 1, 1,-1};
queue <coordonate> Q1,Q2;
void leeRomeo ( coordonate start )
{
int i = start.x;
int j = start.y;
Romeo[i][j] = 1;
Q1.push(start); /// adaug in coada
while ( !Q1.empty() ) /// cat timp coada nu este vida
{
coordonate varf = Q1.front();
Q1.pop();
i = varf.x;
j = varf.y; /// extrag din coada varful cozii
for ( int k = 1; k <= 8; k++ )
{
int ox = i + dx[k];
int oy = j + dy[k]; ///coordonatele vecinilor
if ( Romeo[ox][oy] == 0 ) /// daca vecinul se afla in matrice si pot ajunge la el
{
Romeo[ox][oy] = Romeo[i][j] + 1;
coordonate vecin;
vecin.x = ox;
vecin.y = oy;
Q1.push(vecin); /// bag vecinii in coada
}
}
}
}
void leeJulieta ( coordonate start )
{
int i = start.x;
int j = start.y;
Julieta[i][j] = 1;
Q2.push(start);
while ( !Q2.empty() )
{
coordonate varf = Q2.front();
Q2.pop();
i = varf.x;
j = varf.y; /// extrag din coada varful cozii
for ( int k = 1; k <= 8; k++ )
{
int ox = i + dx[k];
int oy = j + dy[k]; ///coordonatele vecinilor
if ( Julieta[ox][oy] == 0 ) /// daca vecinul se afla in matrice si pot ajunge la el
{
Julieta[ox][oy] = Julieta[i][j] + 1;
coordonate vecin;
vecin.x = ox;
vecin.y = oy;
Q2.push(vecin); /// bag vecinii in coada
}
}
}
}
int main()
{
f>>n>>m;
f.get();
intalnire.x = -1;
intalnire.y = -1;
for(int i=1; i<=n; i++)
{
f.getline(linie,101);
for(int j=0; j<n; j++)
{
if(linie[j] == 'X')
{
Romeo[i][j+1] = -1;
Julieta[i][j+1] = -1;
}
if(linie[j] == 'R')
{
romeo.x = i;
romeo.y = j+1;
Julieta[i][j+1] = -1;
}
if(linie[j] == 'J')
{
julieta.x = i;
julieta.y = j+1;
Romeo[i][j+1] = -1;
}
}
}
for (int i = 0; i <= m + 1; i++)
Romeo[0][i] = Romeo[n + 1][i] = Julieta[0][i] = Julieta[n + 1][i] = -1;
for (int i = 0; i <= n + 1; i++)
Romeo[i][0] = Romeo[i][m + 1] = Julieta[i][0] = Julieta[i][m + 1] = -1;
leeRomeo(romeo);
leeJulieta(julieta);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
if (Romeo[i][j] == Julieta[i][j] )
if( Julieta[i][j]!= -1 && Julieta[i][j]!= 0)
if (Julieta[i][j] < minim)
{
minim = Julieta[i][j];
intalnire.x = i;
intalnire.y = j;
}
}
g<<minim<<" "<<intalnire.x<<" "<<intalnire.y;
return 0;
}