Nu aveti permisiuni pentru a descarca fisierul grader_test5.ok
Cod sursa(job #1140491)
Utilizator | Data | 12 martie 2014 01:13:19 | |
---|---|---|---|
Problema | Rj | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.81 kb |
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
bool vizr[102][102],vizj[102][102];
int matr[102][102];
int n,m,x,y;
char c;
int xr,yr,xj,yj;
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
pair<int,int> aux,aux1;
bool ok(int x, int y)
{
return (x>=1 && y>=1 && x<=n && y<=m ) ;
}
int parg(int xr,int yr, int xj, int yj)
{
queue< pair<int, int> > R,J;
int nrr=0, nrj=0;
R.push(make_pair(xr,yr));
J.push(make_pair(xj,yj));
vizr[xr][yr]=1;
vizj[xj][yj]=1;
while(!R.empty() && !J.empty())
{
aux=R.front();
while(nrr == matr[aux.first][aux.second])
{
for(int k=0;k<8;k++)
{
int ll=aux.first+dl[k]; int cc=aux.second+dc[k];
if( !vizr[ll][cc] && matr[ll][cc]>=0 && ok(ll,cc) )
{
R.push( make_pair(ll,cc) );
vizr[ll][cc]=1;
matr[ll][cc]=matr[aux.first][aux.second]+1;
}
}
R.pop(); aux=R.front();
}
nrr++;
aux=J.front();
while(nrj == matr[aux.first][aux.second])
{
for(int k=0;k<8;k++)
{
int ll=aux.first+dl[k]; int cc=aux.second+dc[k];
if( vizr[ll][cc] && matr[ll][cc]==nrj+1 )
{
x=ll;
y=cc;
return matr[aux.first][aux.second]+2;
}
if( !vizj[ll][cc] && matr[ll][cc]>=0 && ok(ll,cc) )
{
J.push( make_pair(ll,cc) );
vizj[ll][cc]=1;
matr[ll][cc]=matr[aux.first][aux.second]+1;
}
}
J.pop(); aux=J.front();
}
nrj++;
}
}
int main()
{
freopen("rj.in","rt",stdin);
freopen("rj.out","wt",stdout);
scanf("%d%d%c",&n,&m,&c);
for(register int i=1;i<=n;i++,scanf("%c",&c))
for(register int j=1;j<=m;j++)
{
scanf("%c",&c);
if(c=='X') matr[i][j]=-1;
if(c=='R') {xr=i; yr=j;}
if(c=='J') {xj=i; yj=j;}
}
int rez=parg(xr,yr,xj,yj);
printf("%d %d %d\n",rez,x,y);
return 0;
}