Mai intai trebuie sa te autentifici.
Cod sursa(job #1734506)
Utilizator | Data | 27 iulie 2016 15:49:12 | |
---|---|---|---|
Problema | Rj | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.15 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int di[8] = { 1,0,-1,0,-1,-1,1,1 };
int dj[8] = { 0,-1,0,1,-1,1,1,-1 };
int n,m,i,j,strx,stry,stjx,stjy,strtx,strty,x,y,tmin,mn=100000,ro,ju,d;
int t[150][150],q[150][150],f[150][150];
string s;
queue < pair < int,int > > coada,c;
bool ok(int ii, int jj)
{
if (ii<1) return false;
if (jj<1) return false;
if (ii>n) return false;
if (jj>m) return false;
return true;
}
void atribuire()
{
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
q[i][j]=t[i][j];
}
void lee()
{
int i,j,iu,ju;
while (!coada.empty())
{
i=coada.front().first;
j=coada.front().second;
coada.pop();
for (int directie=0; directie<=7; directie++)
{
iu=i+di[directie];
ju=j+dj[directie];
if (ok(iu,ju) && t[iu][ju]==0)
{
t[iu][ju]=t[i][j]+1;
coada.push(make_pair(iu,ju));
}
}
}
}
void lee1()
{
int i,j,iu,ju;
while (!c.empty())
{
i=c.front().first;
j=c.front().second;
c.pop();
for (int directie=0; directie<=7; directie++)
{
iu=i+di[directie];
ju=j+dj[directie];
if (ok(iu,ju) && q[iu][ju]==0)
{
q[iu][ju]=q[i][j]+1;
c.push(make_pair(iu,ju));
}
}
}
}
int main()
{
fin>>n>>m;
getline(fin,s);
for (i=1; i<=n; i++)
{
getline(fin,s);
for (j=0; j<m; j++)
{
if (s[j]=='R') { strx=i; stry=j+1; coada.push(make_pair(i,j+1)); }
if (s[j]=='J') { stjx=i; stjy=j+1; c.push(make_pair(i,j+1)); }
if (s[j]=='X') { t[i][j+1]=-1; }
}
}
atribuire();
lee();
lee1();
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
if (t[i][j]==q[i][j] && t[i][j]>0)
if (t[i][j]+1<mn ) { mn=t[i][j]+1; ro=i; ju=j; }
}
fout<<mn<<" "<<ro<<" "<<ju<<"\n";
return 0;
}