Pagini recente » Cod sursa (job #2658393) | Cod sursa (job #197605) | Cod sursa (job #2527691) | Cod sursa (job #1950295) | Cod sursa (job #344780)
Cod sursa(job #344780)
#include <stdio.h>
#include <queue>
#include <string.h>
#define MAXN 102
using namespace std;
char h[MAXN][MAXN];
bool viz[MAXN][MAXN];
int timp[MAXN][MAXN],jl[MAXN][MAXN];
struct point
{
int x,y;
point()
{
}
point(int v1,int v2)
{
x = v1;
y = v2;
}
};
queue<point> q;
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
int n,m,i,j;
char aux;
point temp,jul;
scanf("%d%d\n",&n,&m);
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
scanf("%c",&h[i][j]);
if (h[i][j] == 'R')
{
temp.x = j;
temp.y = i;
q.push(temp);
viz[temp.y][temp.x] = true;
}
if (h[i][j] == 'J')
{
jul.x = j;
jul.y = i;
}
}
scanf("%c",&aux);
}
int x,y;
while (!q.empty())
{
x = q.front().x;
y = q.front().y;
if (x > 1)
{
if (!viz[y][x-1] && h[y][x-1] != 'X')
{
viz[y][x-1] = true;
timp[y][x-1] = timp[y][x]+1;
q.push(point(x-1,y));
}
}
if (x<m)
{
if (!viz[y][x+1] && h[y][x+1] != 'X')
{
viz[y][x+1] = true;
timp[y][x+1] = timp[y][x]+1;
q.push(point(x+1,y));
}
}
if (y > 1)
{
if (!viz[y-1][x] && h[y-1][x] != 'X')
{
viz[y-1][x] = true;
timp[y-1][x] = timp[y][x]+1;
q.push(point(x,y-1));
}
}
if (y<n)
{
if (!viz[y+1][x] && h[y+1][x] != 'X')
{
viz[y+1][x] = true;
timp[y+1][x] = timp[y][x]+1;
q.push(point(x,y+1));
}
}
q.pop();
}
memset(viz,0,sizeof(viz));
q.push(jul);
viz[jul.y][jul.x] = true;
int best = 99999999,bx,by;
while (!q.empty())
{
x = q.front().x;
y = q.front().y;
if (x > 1)
{
if (!viz[y][x-1] && h[y][x-1] != 'X')
{
viz[y][x-1] = true;
jl[y][x-1] = jl[y][x]+1;
q.push(point(x-1,y));
if (jl[y][x-1] == timp[y][x-1] && best>jl[y][x-1])
{
best = jl[y][x-1];
bx = x-1;
by = y;
}
}
}
if (x<m)
{
if (!viz[y][x+1] && h[y][x+1] != 'X')
{
viz[y][x+1] = true;
jl[y][x+1] = jl[y][x]+1;
q.push(point(x+1,y));
if (jl[y][x+1] == timp[y][x+1] && best>jl[y][x+1])
{
best = jl[y][x+1];
bx = x+1;
by = y;
}
}
}
if (y > 1)
{
if (!viz[y-1][x] && h[y-1][x] != 'X')
{
viz[y-1][x] = true;
jl[y-1][x] = jl[y][x]+1;
q.push(point(x,y-1));
if (jl[y-1][x] == timp[y-1][x] && best>jl[y-1][x])
{
best = jl[y-1][x];
bx = x;
by = y-1;
}
}
}
if (y<n)
{
if (!viz[y+1][x] && h[y+1][x] != 'X')
{
viz[y+1][x] = true;
jl[y+1][x] = jl[y][x]+1;
q.push(point(x,y+1));
if (jl[y+1][x] == timp[y+1][x] && best>jl[y+1][x])
{
best = jl[y+1][x];
bx = x;
by = y+1;
}
}
}
q.pop();
}
printf("%d %d %d",best,by,bx);
return 0;
}