Pagini recente » Cod sursa (job #638569) | Cod sursa (job #409419) | Cod sursa (job #895024) | Monitorul de evaluare | Cod sursa (job #1456953)
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct pozitie
{
int i;
int j;
};
pozitie pr, pj;
pozitie pc, pu;
queue <pozitie> q;
int a[101][101];
int oro[101][101];
int oju[101][101];
string x[101];
int main()
{
int n, m;
int i, j;
int minim=100000000;
int imin=0, jmin=0;
fin >> n >> m;
for(i=0; i<=n; i++)
getline(fin, x[i]);
for(i=0; i<=n; i++)
for(j=0; j<m; j++)
{
if(x[i][j]==' ')
a[i][j+1]=0;
if(x[i][j]=='X')
a[i][j+1]=1;
if(x[i][j]=='R')
{
a[i][j+1]=0;
pr.i=i;
pr.j=j+1;
}
if(x[i][j]=='J')
{
a[i][j+1]=0;
pj.i=i;
pj.j=j+1;
}
}
for(j=0; j<=m+1; j++)
{
a[0][j]=1;
a[n+1][j]=1;
}
for(i=0; i<=n+1; i++)
{
a[i][0]=1;
a[i][m+1]=1;
}
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
oro[i][j]=10001;
oju[i][j]=10001;
}
oro[pr.i][pr.j]=1;
q.push(pr);
while(!q.empty())
{
pc=q.front();q.pop();
pu.i=pc.i; pu.j=pc.j+1;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i; pu.j=pc.j-1;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i-1; pu.j=pc.j;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i+1; pu.j=pc.j;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i+1; pu.j=pc.j+1;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i-1; pu.j=pc.j-1;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i-1; pu.j=pc.j+1;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i+1; pu.j=pc.j-1;
if(a[pu.i][pu.j]==0)
if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
{
oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
q.push(pu);
}
}
oju[pj.i][pj.j]=1;
q.push(pj);
while(!q.empty())
{
pc=q.front();q.pop();
pu.i=pc.i; pu.j=pc.j+1;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i; pu.j=pc.j-1;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i-1; pu.j=pc.j;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i+1; pu.j=pc.j;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i+1; pu.j=pc.j+1;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i-1; pu.j=pc.j-1;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i-1; pu.j=pc.j+1;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
pu.i=pc.i+1; pu.j=pc.j-1;
if(a[pu.i][pu.j]==0)
if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
{
oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
q.push(pu);
}
}
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
if(oro[i][j]==oju[i][j] && oro[i][j]<minim)
{
minim=oro[i][j];
imin=i;
jmin=j;
}
fout << minim << " " << imin << " " << jmin;
return 0;
}