Pagini recente » Cod sursa (job #680614) | Cod sursa (job #3280682) | Cod sursa (job #2674700) | Cod sursa (job #470000) | Cod sursa (job #345136)
Cod sursa(job #345136)
#include <stdio.h>
#include <queue>
#include <string.h>
#define MAXN 128
using namespace std;
int dir[16] = {0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
struct point
{
int x,y;
point(int vx,int vy)
{
x = vx;
y = vy;
}
point()
{
}
};
char h[MAXN][MAXN];
int n,m,i,k;
int r[MAXN][MAXN],j[MAXN][MAXN];
bool viz[MAXN][MAXN];
int best = 99999999,maxx,maxy;
queue<point> q;
void solve()
{
for (i=1;i<=n;i++)
{
for (k=1;k<=m;k++)
{
if (r[i][k] == j[i][k] && best>r[i][k] && viz[i][k])
{
best = r[i][k];
maxx = k;
maxy = i;
}
}
}
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
scanf("%d%d\n",&n,&m);
char aux;
point jf,rf;
for (i=1;i<=n;i++)
{
for (k=1;k<=m;k++)
{
scanf("%c",&h[i][k]);
if (h[i][k] == 'R')
{
rf.x = k;
rf.y = i;
}
if (h[i][k] == 'J')
{
jf.x = k;
jf.y = i;
}
}
scanf("%c",&aux);
}
q.push(rf);
memset(viz,0,sizeof(viz));
viz[rf.y][rf.x] = true;
r[rf.y][rf.x] = true;
int x,y;
for (i=0;i<=n+1;i++)
{
viz[i][0] = true;
viz[i][m+1] = true;
}
for (i=0;i<=m+1;i++)
{
viz[0][i] = true;
viz[n+1][i] = true;
}
while (!q.empty())
{
x = q.front().x;
y = q.front().y;
for (i=0;i<=16;i+=2)
{
if (!viz[y+dir[i]][x+dir[i+1]] && h[y+dir[i]][x+dir[i+1]] != 'X')
{
q.push(point(x+dir[i+1],y+dir[i]));
viz[y+dir[i]][x+dir[i+1]] = true;
r[y+dir[i]][x+dir[i+1]] = r[y][x] + 1;
}
}
q.pop();
}
q.push(jf);
memset(viz,0,sizeof(viz));
for (i=0;i<=n+1;i++)
{
viz[i][0] = true;
viz[i][m+1] = true;
}
for (i=0;i<=m+1;i++)
{
viz[0][i] = true;
viz[n+1][i] = true;
}
viz[jf.y][jf.x] = true;
j[jf.y][jf.x] = true;
while (!q.empty())
{
x = q.front().x;
y = q.front().y;
for (i=0;i<=16;i+=2)
{
if (!viz[y+dir[i]][x+dir[i+1]] && h[y+dir[i]][x+dir[i+1]] != 'X')
{
q.push(point(x+dir[i+1],y+dir[i]));
viz[y+dir[i]][x+dir[i+1]] = true;
j[y+dir[i]][x+dir[i+1]] = j[y][x] + 1;
}
}
q.pop();
}
solve();
printf("%d %d %d",best,maxy,maxx);
return 0;
}