Mai intai trebuie sa te autentifici.
Cod sursa(job #1290006)
Utilizator | Data | 10 decembrie 2014 18:17:19 | |
---|---|---|---|
Problema | Rj | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.22 kb |
#include<fstream>
#include<queue>
using namespace std;
char a[115][115];
int L,C,b[115][115],c[115][115],xr,yr,xj,yj;
struct coord
{
int x,y,pas;
};
int dx[]={-1,1,0,0,-1,1,-1,1};
int dy[]={0,0,-1,1,-1,1,1,-1};
void Citire()
{
int i, j;
ifstream fin("rj.in");
fin>>L>>C;
fin.get();
for(i=1;i<=L;i++)
fin.getline(a[i]+1,105);
for(i=1;i<=L;i++)
for(j=1;j<=C;j++)
if(a[i][j]== 'R')
{
xr=i;
yr=j;
}
else if(a[i][j]=='J')
{
xj=i;
yj=j;
}
}
void Bordare()
{
int i;
for(i=0;i<=L+1;i++)
a[i][0]=a[i][C+1]='X';
for(i=0;i<=C+1;i++)
a[0][i]=a[L+1][i]='X';
}
void LeeR()
{
int k;
queue <coord> q;
coord w, w1;
w.x=xr;
w.y=yr;
w.pas=1;
b[xr][yr]=1;
q.push(w);
while(!q.empty())
{
w=q.front();
q.pop();
for (k = 0 ; k < 8; k++)
{
w1.x=w.x+dx[k];
w1.y=w.y+dy[k];
w1.pas=w.pas+1;
if((a[w1.x][w1.y]!='X')&&(b[w1.x][w1.y]==0||b[w1.x][w1.y]>w1.pas))
{
b[w1.x][w1.y]=w1.pas;
q.push(w1);
}
}
}
}
void LeeJ()
{
int k;
queue <coord> q;
coord w, w1;
w.x=xj;
w.y=yj;
w.pas=1;
c[xj][yj]=1;
q.push(w);
while(!q.empty())
{
w=q.front();
q.pop();
for(k=0;k<8;k++)
{
w1.x=w.x+dx[k];
w1.y=w.y+dy[k];
w1.pas=w.pas+1;
if((a[w1.x][w1.y]!='X')&&(c[w1.x][w1.y]==0||c[w1.x][w1.y]>w1.pas))
{
c[w1.x][w1.y]=w1.pas;
q.push(w1);
}
}
}
}
void Afisare()
{
ofstream fout ("rj.out");
int i,j,xf,yf,minim=1000000000;
xf=yf=0;
for(i=1;i<=L;i++)
for(j=1;j<=C;j++)
if(b[i][j]==c[i][j]&&b[i][j]!=0&&minim>b[i][j])
{
minim=b[i][j];
xf=i;
yf=j;
}
fout<<minim<<" "<<xf<<" "<<yf<<"\n";
}
int main()
{
Citire();
Bordare();
LeeR();
LeeJ();
Afisare();
return 0;
}