Pagini recente » Cod sursa (job #2665486) | Cod sursa (job #2762731) | Cod sursa (job #627984) | Cod sursa (job #3039419) | Cod sursa (job #2468646)
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const int DMAX = 100; ///Dimensiunea maxima a labirintului
struct pozitie
{
short int x, y;
};
int M, N, J[DMAX + 2][DMAX + 2], R[DMAX + 2][DMAX + 2];
pozitie C[DMAX * DMAX + 1];
pozitie C2[DMAX * DMAX + 1];
int p, u;
pozitie Romeo;
pozitie Julieta;
int d[8][2] = {{0, -1}, { -1, 0}, {0, 1}, {1, 0}, { -1, 1}, {1, 1}, {1, -1}, { -1, -1}};
void bordare()
{
int i;
for(i = 0; i <= N + 1; i++)
R[i][0] = R[i][M + 1] = -1;
for(i = 1; i <= M; i++)
R[0][i] = R[N + 1][i] = -1;
}
void bordare2()
{
int i;
for(i = 0; i <= N + 1; i++)
J[i][0] = J[i][M + 1] = -1;
for(i = 1; i <= M; i++)
J[0][i] = J[N + 1][i] = -1;
}
void Lee()
{
pozitie vec, crt;
p = u = 1;
C[1] = Romeo; ///Se pune in coada pozitia initiala a soricelului
while(p <= u) ///Cat timp coada ete nevida si nu s a ajuns la cascaval
{
crt = C[p++]; ///Se extrage un elem,ent din coada
for(int k = 0; k < 8; k++) ///se parcurg vecinii pozitie curente{
{
vec.x = crt.x + d[k][0]; ///Se obtin coordonatele vecinului
vec.y = crt.y + d[k][1];
if(R[vec.x][vec.y] == 0) ///Vecinul este un culoar nevizitat
{
R[vec.x][vec.y] = R[crt.x][crt.y] + 1; ///Creste disntanta minima
C[++u] = vec; ///Adaugare vecin in coada
}
}
}
}
void Lee2()
{
pozitie VEC, CRT;
p = u = 1;
C2[1] = Julieta; ///Se pune in coada pozitia initiala a soricelului
while(p <= u) ///Cat timp coada ete nevida si nu s a ajuns la cascaval
{
CRT = C2[p++]; ///Se extrage un elem,ent din coada
for(int k = 0; k < 8; k++) ///se parcurg vecinii pozitie curente{
{
VEC.x = CRT.x + d[k][0]; ///Se obtin coordonatele vecinului
VEC.y = CRT.y + d[k][1];
if(J[VEC.x][VEC.y] == 0) ///Vecinul este un culoar nevizitat
{
J[VEC.x][VEC.y] = J[CRT.x][CRT.y] + 1; ///Creste disntanta minima
C2[++u] = VEC; ///Adaugare vecin in coada
}
}
}
}
void citire()
{
char lin[DMAX + 2];
f >> N >> M;
f.get();
for(int i = 1; i <= N; i++)
{
f.get(lin, DMAX + 2);
for(int j = 1; j <= M; j++)
switch(lin[j - 1])
{
case 'X':
J[i][j] = -1;
R[i][j] = -1;
break;
case ' ':
J[i][j] = 0;
R[i][j] = 0;
break;
case 'R':
Romeo.x = i;
Romeo.y = j;
R[i][j] = 1;
J[i][j] = 0;
break;
case 'J':
Julieta.x = i;
Julieta.y = j;
J[i][j] = 1;
R[i][j] = 0;
}
f.get();
}
}
void Afis()
{
int tmin = DMAX * DMAX + 5, xmin = -1, ymin = -1, i, k;
for (i = 1; i <= N; i++)
for (k = 1; k <= M; k++)
if (R[i][k] == J[i][k])
if (R[i][k] < tmin && R[i][k] != -1)
{
tmin = R[i][k];
xmin = i;
ymin = k;
}
g << tmin << ' ' << xmin << ' ' << ymin << '\n';
}
int main()
{
citire();
bordare();
Lee();
bordare2();
Lee2();
Afis();
return 0;
}