Cod sursa(job #1561700)
Utilizator | Data | 4 ianuarie 2016 14:01:25 | |
---|---|---|---|
Problema | Rj | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.11 kb |
#include <cstdio>
using namespace std;
int dx[]={0 ,0 ,1 ,-1, 1, 1, -1, -1};
int dy[]={1 ,-1 ,0, 0, 1, -1, 1, -1};
char c1;
int Min,tmin,p1,p2,i,j,xr,yr,xj,yj,m,n,u,s,p,tr[101][101],tj[101][101];
bool r[101][101],j2[101][101];
struct elem
{
int l,c;
}c[10001],d[10001],x,z;
void r1()
{
p=1;
c[1].l=xr;
c[1].c=yr;
tr[xr][yr]=1;
u=1;
while(p <= u)
{
z=c[p];
++p;
for(int i=0;i<8;++i)
{
x.l=z.l+dx[i];
x.c=z.c+dy[i];
if((x.l>0&&x.c>0)&&(x.c<=m&&x.l<=n))
if(r[x.l][x.c]==0&&(tr[x.l][x.c]>tr[z.l][z.c]+1))
{
r[x.l][x.c]=1;
++u;
c[u]=x;
tr[x.l][x.c]=tr[z.l][z.c]+1;
}
}
}
}
void j1()
{
p=1;
c[1].l=xj;
c[1].c=yj;
tj[xj][yj]=1;
u=1;
while(p<=u)
{
z=c[p];
++p;
for(int i=0;i<8;++i)
{
x.l=z.l+dx[i];
x.c=z.c+dy[i];
if((x.l>0&&x.c>0)&&(x.c<=m&&x.l<=n))
{
if(j2[x.l][x.c]==0&&(tj[x.l][x.c]>tj[z.l][z.c]+1))
{
j2[x.l][x.c]=1;
++u;
c[u]=x;
tj[x.l][x.c]=tj[z.l][z.c]+1;
}
}
}
}
}
int Max1(int x, int y)
{
if(x>y) return x;
else return y;
}
int main ()
{
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i=1;i<=n;++i)
{
scanf("%c", &c1);
for(j=1;j<=m;++j)
{
scanf("%c", &c1);
if(c1=='R')
{
xr=i;
yr=j;
}
else if(c1=='J')
{
xj=i;
yj=j;
}
else if(c1=='X')
{
r[i][j]=1;
j2[i][j]=1;
}
tr[i][j]=100000;
tj[i][j]=100000;
}
}
r1();
j1();
tmin=100000;
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
if(tr[i][j]==tj[i][j]&&(tr[i][j]!=100000&&tj[i][j]!=100000))
{
if(tmin>tr[i][j])
{
tmin=tr[i][j];
p1=i;
p2=j;
}
// else if(tr[i][j]==tmin)
// {
// if(i<p1)
// {
// tmin=tr[i][j];
// p1=i;
// p2=j;
// }
// else if(j<p2&&i==p1)
// {
// tmin=tr[i][j];
// p1=i;
// p2=j;
// }
// }
}
}
}
printf("%d %d %d\n", tmin, p1, p2);
return 0;
}