Pagini recente » Cod sursa (job #2778541) | Cod sursa (job #2695343) | Cod sursa (job #3197552) | Cod sursa (job #3256694) | Cod sursa (job #577322)
Cod sursa(job #577322)
#include <fstream>
using namespace std;
short a[110][110], n, m, b[110][110], c[110][110], n1, m1, xr, yr, xj, yj, xf, yf=32000, tmin=32000;
char s[110];
struct Coada
{
int x, y;
};
Coada coada[100010];
void Romeo ()
{
int x, y, st, dr, w;
x=xr;
y=yr;
st=0;
dr=0;
if (a[x-1][y]==0)
{
b[x-1][y]=1;
coada[dr].x=x-1;
coada[dr++].y=y;
}
if (a[x-1][y+1]==0)
{
b[x-1][y+1]=1;
coada[dr].x=x-1;
coada[dr++].y=y+1;
}
if (a[x][y+1]==0)
{
b[x][y+1]=1;
coada[dr].x=x;
coada[dr++].y=y+1;
}
if (a[x+1][y+1]==0)
{
b[x+1][y+1]=1;
coada[dr].x=x+1;
coada[dr++].y=y+1;
}
if (a[x+1][y]==0)
{
b[x+1][y]=1;
coada[dr].x=x+1;
coada[dr++].y=y;
}
if (a[x+1][y-1]==0)
{
b[x+1][y-1]=1;
coada[dr].x=x+1;
coada[dr++].y=y-1;
}
if (a[x][y-1]==0)
{
b[x][y-1]=1;
coada[dr].x=x;
coada[dr++].y=y-1;
}
if (a[x-1][y-1]==0)
{
b[x-1][y-1]=1;
coada[dr].x=x-1;
coada[dr++].y=y-1;
}
while (st<dr)
{
x=coada[st].x;
y=coada[st].y;
w=b[x][y];
if (a[x-1][y]==0 && b[x-1][y]==0)
{
b[x-1][y]=w+1;
coada[dr].x=x-1;
coada[dr++].y=y;
}
if (a[x-1][y+1]==0 && b[x-1][y+1]==0)
{
b[x-1][y+1]=1+w;
coada[dr].x=x-1;
coada[dr++].y=y+1;
}
if (a[x][y+1]==0 && b[x][y+1]==0)
{
b[x][y+1]=1+w;
coada[dr].x=x;
coada[dr++].y=y+1;
}
if (a[x+1][y+1]==0 && b[x+1][y+1]==0)
{
b[x+1][y+1]=w+1;
coada[dr].x=x+1;
coada[dr++].y=y+1;
}
if (a[x+1][y]==0 && b[x+1][y]==0)
{
b[x+1][y]=w+1;
coada[dr].x=x+1;
coada[dr++].y=y;
}
if (a[x+1][y-1]==0 && b[x+1][y-1]==0)
{
b[x+1][y-1]=w+1;
coada[dr].x=x+1;
coada[dr++].y=y-1;
}
if (a[x][y-1]==0 && b[x][y-1]==0)
{
b[x][y-1]=w+1;
coada[dr].x=x;
coada[dr++].y=y-1;
}
if (a[x-1][y-1]==0 && b[x-1][y-1]==0)
{
b[x-1][y-1]=w+1;
coada[dr].x=x-1;
coada[dr++].y=y-1;
}
st++;
}
}
void Julieta ()
{
int x, y, st, dr, w;
x=xj;
y=yj;
st=0;
dr=0;
if (a[x-1][y]==0)
{
c[x-1][y]=1;
coada[dr].x=x-1;
coada[dr++].y=y;
}
if (a[x-1][y+1]==0)
{
c[x-1][y+1]=1;
coada[dr].x=x-1;
coada[dr++].y=y+1;
}
if (a[x][y+1]==0)
{
c[x][y+1]=1;
coada[dr].x=x;
coada[dr++].y=y+1;
}
if (a[x+1][y+1]==0)
{
c[x+1][y+1]=1;
coada[dr].x=x+1;
coada[dr++].y=y+1;
}
if (a[x+1][y]==0)
{
c[x+1][y]=1;
coada[dr].x=x+1;
coada[dr++].y=y;
}
if (a[x+1][y-1]==0)
{
c[x+1][y-1]=1;
coada[dr].x=x+1;
coada[dr++].y=y-1;
}
if (a[x][y-1]==0)
{
c[x][y-1]=1;
coada[dr].x=x;
coada[dr++].y=y-1;
}
if (a[x-1][y-1]==0)
{
c[x-1][y-1]=1;
coada[dr].x=x-1;
coada[dr++].y=y-1;
}
while (st<dr)
{
x=coada[st].x;
y=coada[st].y;
w=c[x][y];
if (a[x-1][y]==0 && c[x-1][y]==0)
{
c[x-1][y]=w+1;
coada[dr].x=x-1;
coada[dr++].y=y;
}
if (a[x-1][y+1]==0 && c[x-1][y+1]==0)
{
c[x-1][y+1]=1+w;
coada[dr].x=x-1;
coada[dr++].y=y+1;
}
if (a[x][y+1]==0 && c[x][y+1]==0)
{
c[x][y+1]=1+w;
coada[dr].x=x;
coada[dr++].y=y+1;
}
if (a[x+1][y+1]==0 && c[x+1][y+1]==0)
{
c[x+1][y+1]=w+1;
coada[dr].x=x+1;
coada[dr++].y=y+1;
}
if (a[x+1][y]==0 && c[x+1][y]==0)
{
c[x+1][y]=w+1;
coada[dr].x=x+1;
coada[dr++].y=y;
}
if (a[x+1][y-1]==0 && c[x+1][y-1]==0)
{
c[x+1][y-1]=w+1;
coada[dr].x=x+1;
coada[dr++].y=y-1;
}
if (a[x][y-1]==0 && c[x][y-1]==0)
{
c[x][y-1]=w+1;
coada[dr].x=x;
coada[dr++].y=y-1;
}
if (a[x-1][y-1]==0 && c[x-1][y-1]==0)
{
c[x-1][y-1]=w+1;
coada[dr].x=x-1;
coada[dr++].y=y-1;
}
st++;
}
}
void Suprapunere ()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if (b[i][j]==c[i][j] && b[i][j]!=0)
if (b[i][j]<tmin)
{
tmin=b[i][j];
xf=i;
yf=j;
}
}
int main ()
{
ifstream f("rj.in");
f>>n>>m;
int i, j;
char ch;
f.get();
for (i=1; i<=n; i++)
{
f.get (s, 110);
for (j=1; j<=m; j++)
{
ch=s[j-1];
if (ch!='R' && ch!='J')
if (ch==' ')
a[i][j]=0;
else
a[i][j]=1;
else
if (ch=='R')
{
a[i][j]=2;
xr=i;
yr=j;
}
else
{
xj=i;
yj=j;
a[i][j]=3;
}
}
f.get();
}
f.close();
n1=n+1;
m1=m+1;
for (i=0; i<=n1; i++)
{
a[i][0]=-14;
a[i][m1]=-14;
}
for (i=0; i<=m1; i++)
{
a[0][i]=-14;
a[n1][i]=-14;
}
Romeo ();
Julieta ();
Suprapunere ();
ofstream g("rj.out");
g<<tmin+1<<" "<<xf<<" "<<yf<<"\n";
g.close();
return 0;
}