Cod sursa(job #1824669)
Utilizator | Data | 8 decembrie 2016 11:12:24 | |
---|---|---|---|
Problema | Rj | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.52 kb |
#include <fstream>
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
const int nmax=100;
int v[nmax+2][nmax+2];
int qx[nmax*nmax+1],qy[nmax*nmax+1];
int dx[]={0,0,-1,+1},dy[]={+1,-1, 0, 0};
int main()
{
int n,m;
in>>n>>m;
string s;
//getline(in,s);
int qb=1 , qe=2;
for(int i = 1; i <= n; i++)
{
getline(in,s);
for(int j=1; j <= m; j++)
{
if(s[j-1]=='R')
{
v[i][j]=1;
qx[1]=i;
qy[1]=j;
}
if(s[j-1]=='J')
{
v[i][j]=nmax*nmax+1;
qx[2]=i;
qy[2]=j;
}
if(s[j-1]=='X')
v[i][j]=-1;
}
}
for(int i=0; i<=n+1; i++)
{
v[i][0]=-1;
v[i][m+1]=-1;
}
for(int i=0; i<=m+1; i++)
{
v[0][i]=-1;
v[n+1][i]=-1;
}
int sol=nmax*nmax+1,solx=0,soly=0;
while(qb<=qe)
{
int x,y;
x=qx[qb];
y=qy[qb];
qb++;
for(int i=0; i<4; i++)
{
int xn,yn;
xn=x+dx[i];
yn=y+dy[i];
if(v[xn][yn]==0)
{
qe++;
v[xn][yn]=v[x][y]+1;
qx[qe]=xn;
qy[qe]=yn;
}
if (v[xn][yn]!=0 && v[xn][yn]!=-1) {
if( (v[x][y]<nmax*nmax && v[xn][yn]>nmax*nmax)||
(v[x][y]>nmax*nmax && v[xn][yn]<nmax*nmax) )
{
int a=v[x][y],b=v[xn][yn];
if(a>b)
{
a=a-nmax*nmax;
}
else
{
b=b-nmax*nmax;
}
if(a+1>=b)
{
if(sol>a+1 ||
(sol==a+1 && solx>xn) ||
(sol==a+1 && solx==xn && soly>yn))
{
sol=a+1;
solx=xn;
soly=yn;
}
}
if(b>=a+1)
{
if(sol>b ||
(sol==b && solx>xn) ||
(sol==b && solx==xn && soly>yn))
{
sol=b;
solx=xn;
soly=yn;
}
}
if(a>=b+1)
{
if(sol>a||
(sol==a && solx>x) ||
(sol==a && solx==x && soly>y))
{
sol=a;
solx=x;
soly=y;
}
}
if(b+1>=a)
{
if(sol>b+1 ||
(sol==b+1 && solx>x)||
(sol==b+1 && solx==x && soly>y))
{
sol=b+1;
solx=x;
soly=y;
}
}
}
}
}
}
out<<sol-1<<" "<<solx<<" "<<soly<<'\n';
return 0;
}