Cod sursa(job #891409)
Utilizator | Data | 25 februarie 2013 16:36:37 | |
---|---|---|---|
Problema | Rj | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 12.22 kb |
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
struct element {unsigned char x,y;}c[10500];
struct vector {int val;bool atins;}v[105][105];
int n,i,j,m,xRomeo,xJulieta,yRomeo,yJulieta,g,mini=999999,minj=99999,pasmaxim=9999999,pas;
char s[130];
void Lee_Romeo(int x1,int y1,int x2,int y2)
{
int st=1,dr=1,i,j;
c[st].x=x1;
c[st].y=y1;
v[x1][y1].val=1;
while(st<=dr)
{
i=c[st].x;
j=c[st].y;
if(v[i][j].val+1<v[i][j-1].val)
{
dr++;
c[dr].x=i;
c[dr].y=j-1;
v[i][j-1].val=v[i][j].val+1;
}
if(v[i][j].val+1<v[i+1][j-1].val)
{
dr++;
c[dr].x=i+1;
c[dr].y=j-1;
v[i+1][j-1].val=v[i][j].val+1;
}
if(v[i][j].val+1<v[i-1][j-1].val )
{
dr++;
c[dr].x=i-1;
c[dr].y=j-1;
v[i-1][j-1].val=v[i][j].val+1;
}
if(v[i][j].val+1<v[i][j+1].val)
{
dr++;
c[dr].x=i;
c[dr].y=j+1;
v[i][j+1].val=v[i][j].val+1;
}
if(v[i][j].val+1<v[i+1][j+1].val)
{
dr++;
c[dr].x=i+1;
c[dr].y=j+1;
v[i+1][j+1].val=v[i][j].val+1;
}
if(v[i][j].val+1<v[i-1][j+1].val)
{
dr++;
c[dr].x=i-1;
c[dr].y=j+1;
v[i-1][j+1].val=v[i][j].val+1;
}
if(v[i][j].val+1<v[i+1][j].val)
{
dr++;
c[dr].x=i+1;
c[dr].y=j;
v[i+1][j].val=v[i][j].val+1;
}
if(v[i][j].val+1<v[i-1][j].val)
{
dr++;
c[dr].x=i-1;
c[dr].y=j;
v[i-1][j].val=v[i][j].val+1;
}
st++;
}
}
void Lee_Julieta(int x1,int y1,int x2,int y2)
{
int st=1,dr=1,i,j,ok=1;
c[st].x=x1;
c[st].y=y1;
v[x1][y1].val=1;
while(st<=dr)
{
i=c[st].x;
j=c[st].y;
if(v[i][j].val+1==v[i][j-1].val && v[i][j-1].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i<mini)
{
mini=i;
minj=j-1;
}
if(i==mini)
{
if(j-1<minj)
minj=j-1;
}
}
}
else
if(v[i][j].val+1<v[i][j-1].val)
{
dr++;
c[dr].x=i;
c[dr].y=j-1;
v[i][j-1].val=v[i][j].val+1;
v[i][j-1].atins=1;
}
if(v[i][j].val+1==v[i+1][j-1].val&&v[i+1][j-1].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i+1<mini)
{
mini=i+1;
minj=j-1;
}
if(i+1==mini)
{
if(j-1<minj)
minj=j-1;
}
}
}
else
if(v[i][j].val+1<v[i+1][j-1].val)
{
dr++;
c[dr].x=i+1;
c[dr].y=j-1;
v[i+1][j-1].val=v[i][j].val+1;
v[i+1][j-1].atins=1;
}
if(v[i][j].val+1==v[i-1][j-1].val&&v[i-1][j-1].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i-1<mini)
{
mini=i-1;
minj=j-1;
}
if(i-1==mini)
{
if(j-1<minj)
minj=j-1;
}
}
}
else
if(v[i][j].val+1<v[i-1][j-1].val)
{
dr++;
c[dr].x=i-1;
c[dr].y=j-1;
v[i-1][j-1].val=v[i][j].val+1;
v[i-1][j-1].atins=1;
}
if(v[i][j].val+1==v[i][j+1].val&&v[i][j+1].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i<mini)
{
mini=i;
minj=j+1;
}
if(i==mini)
{
if(j+1<minj)
minj=j+1;
}
}
}
else
if(v[i][j].val+1<v[i][j+1].val)
{
dr++;
c[dr].x=i;
c[dr].y=j+1;
v[i][j+1].val=v[i][j].val+1;
v[i][j+1].atins=1;
}
if(v[i][j].val+1==v[i+1][j+1].val && v[i+1][j+1].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i+1<mini)
{
mini=i+1;
minj=j+1;
}
if(i+1==mini)
{
if(j+1<minj)
minj=j+1;
}
}
}
else
if(v[i][j].val+1<v[i+1][j+1].val)
{
dr++;
c[dr].x=i+1;
c[dr].y=j+1;
v[i+1][j+1].val=v[i][j].val+1;
v[i+1][j+1].atins=1;
}
if(v[i][j].val+1==v[i-1][j+1].val && v[i-1][j+1].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i-1<mini)
{
mini=i-1;
minj=j+1;
}
if(i-1==mini)
{
if(j+1<minj)
minj=j+1;
}
}
}
else
if(v[i][j].val+1<v[i-1][j+1].val)
{
dr++;
c[dr].x=i-1;
c[dr].y=j+1;
v[i-1][j+1].val=v[i][j].val+1;
v[i-1][j+1].atins=1;
}
if(v[i][j].val+1==v[i+1][j].val && v[i+1][j].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i+1<mini)
{
mini=i+1;
minj=j;
}
if(i+1==mini)
{
if(j<minj)
minj=j;
}
}
}
else
if(v[i][j].val+1<v[i+1][j].val)
{
dr++;
c[dr].x=i+1;
c[dr].y=j;
v[i+1][j].val=v[i][j].val+1;
v[i+1][j].atins=1;
}
if(v[i][j].val+1==v[i-1][j].val && v[i-1][j].atins==0)
{
ok=0;
if(pas<=pasmaxim)
{
pasmaxim=pas;
if(i-1<mini)
{
mini=i-1;
minj=j;
}
if(i-1==mini)
{
if(j<minj)
minj=j;
}
}
}
else
if(v[i][j].val+1<v[i-1][j].val)
{
dr++;
c[dr].x=i-1;
c[dr].y=j;
v[i-1][j].val=v[i][j].val+1;
v[i-1][j].atins=1;
}
pas=v[i][j].val+1;
st++;
}
}
int main()
{
in>>n>>m;
in.getline(s,104);
for(i=1;i<=n;i++)
{
in.getline(s,104);
for(j=1;j<=m;j++)
{
if(s[j-1]=='X')
v[i][j].val=-1;
else
if(s[j-1]=='R')
{
xRomeo=i;
yRomeo=j;
}
else
if(s[j-1]=='J')
{
xJulieta=i;
yJulieta=j;
}
else
v[i][j].val=99999999;
}
}
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
if(i==0||i==n+1||j==0||j==m+1)
v[i][j].val=-10000000;
Lee_Romeo(xRomeo,yRomeo,xJulieta,yJulieta);
Lee_Julieta(xJulieta,yJulieta,xRomeo,yRomeo);
out<<v[mini][minj].val<<" "<<mini<<" "<<minj<<'\n';
out.close();
in.close();
return 0;
}