Pagini recente » Cod sursa (job #2062492) | Cod sursa (job #711733) | Cod sursa (job #188458) | Cod sursa (job #1890903) | Cod sursa (job #2293778)
# include<cstdio>
# include<queue>
struct lee
{
int x , y , dist;
};
std :: queue<lee>q;
const int NMAX = 100;
int distanteromeo[NMAX + 1][NMAX + 1];
int distantejulieta[NMAX + 1][NMAX + 1];
int v[NMAX + 1][NMAX + 1];
int dx[] = {0 , -1 , -1 ,0 , 1 , 1 , 1 , 0 , -1};
int dy[] = {0 , 0 , 1 , 1 , 1 , 0 ,- 1, -1 ,- 1};
int main()
{
int n , m , romeox , romeoy , julietax , julietay , ri , rj;
freopen("rj.in" , "r" , stdin);
freopen("rj.out" , "w" , stdout);
scanf("%d%d ", &n , &m);
for(int i = 1; i <= n ; i ++){
for(int j = 1; j <= m; j ++)
{
scanf("%c" , &v[i][j]);
if(v[i][j] == 'R')
{
romeox = i;
romeoy = j;
}
if(v[i][j] == 'J')
{
julietax = i;
julietay = j;
}
distanteromeo[i][j] = distantejulieta[i][j] = 999999999;
}
scanf("\n");
}
q.push({romeox , romeoy , 0});
distanteromeo[romeox][romeoy] = 0;
while(q.empty() == false)
{
lee aux;
aux = q.front();
q.pop();
for(int i = 1; i <= 8 ; i ++)
{
lee next;
next.x = aux.x + dx[i];
next.y = aux.y + dy[i];
next.dist = distanteromeo[aux.x][aux.y] + 1;
if(v[next.x][next.y] == ' ' && distanteromeo[next.x][next.y] > next.dist&& next.x > 0 && next.x <= n && next.y > 0 && next.y <= m)
{
distanteromeo[next.x][next.y] = next.dist;
q.push(next);
}
}
}
q.push({julietax , julietay , 0});
distantejulieta[julietax][julietay] = 0;
while(q.empty() == false)
{
lee aux;
aux = q.front();
q.pop();
for(int i = 1; i <= 8 ; i ++)
{
lee next;
next.x = aux.x + dx[i];
next.y = aux.y + dy[i];
next.dist = distantejulieta[aux.x][aux.y] + 1;
if(v[next.x][next.y] != 'X' && distantejulieta[next.x][next.y] > next.dist && next.x > 0 && next.x <= n && next.y > 0 && next.y <= m)
{
distantejulieta[next.x][next.y] = next.dist;
q.push(next);
}
}
}
int mindist = 100000000;
for(int i = 1; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
{
if(distantejulieta[i][j] == distanteromeo[i][j] && distanteromeo[i][j] != 0)
{
if(mindist > distantejulieta[i][j])
{
mindist = distantejulieta[i][j];
ri = i;
rj = j;
}
}
}
printf("%d %d %d" , mindist + 1, ri , rj);
return 0;
}