Pagini recente » Cod sursa (job #3202348) | OJI2004_11 | Autentificare | Cod sursa (job #2940624) | Cod sursa (job #3208431)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
int n,m,istart,jstart,ifinal,jfinal,v[200][200],w[200][200],i,j;
int di[]={0,0,-1,1},dj[]={1,-1,0,0};
bool inmatrice(int i, int j)
{
return (i>=1 && i<=n && j>=1 && j<=m);
}
void lee()
{
queue <pair<int,int>> q;
q.push(make_pair(istart,jstart));
v[istart][jstart]=1;
while(!q.empty())
{
int icurent=q.front().first,jcurent=q.front().second;
q.pop();
for(int k=0;k<4;k++)
{
int iv=icurent+di[k],jv=jcurent+dj[k];
if(inmatrice(iv,jv) && v[iv][jv]==0)
{
q.push(make_pair(iv,jv));
v[iv][jv]=v[icurent][jcurent]+1;
}
}
if(v[ifinal][jfinal]!=0) break;
}
fout<<(v[ifinal][jfinal]-1)/2<<" ";
}
void lee2()
{
queue <pair<int,int>> q;
q.push(make_pair(ifinal,jfinal));
w[ifinal][jfinal]=1;
while(!q.empty())
{
int icurent=q.front().first,jcurent=q.front().second;
q.pop();
for(int k=0;k<4;k++)
{
int iv=icurent+di[k],jv=jcurent+dj[k];
if(inmatrice(iv,jv) && w[iv][jv]==0)
{
q.push(make_pair(iv,jv));
w[iv][jv]=w[icurent][jcurent]+1;
}
}
if(w[istart][jstart]!=0) break;
}
}
int main()
{
fin>>n>>m; fin.get();
for(i=1;i<=n;i++)
{
char c[200];
fin.getline(c,200);
for(j=1;j<=m;j++)
{
if(c[j-1]==' ') v[i][j]=0;
else if(c[j-1]=='X') v[i][j]=-1;
else if(c[j-1]=='R') {istart=i; jstart=j; v[i][j]=0;}
else { ifinal=i; jfinal=j; v[i][j]=0; }
w[i][j]=v[i][j];
}
}
lee();
lee2();
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(v[i][j]!=-1 && v[i][j]!=0 && v[i][j]==w[i][j]) fout<<i<<" "<<j;
}
}
return 0;
}