Mai intai trebuie sa te autentifici.
Cod sursa(job #3208434)
Utilizator | Data | 28 februarie 2024 17:12:04 | |
---|---|---|---|
Problema | Rj | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 2.34 kb |
#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[]={-1,-1,-1,0,0,1,1,1},dj[]={-1,0,1,-1,1,-1,0,1};
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<8;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;
}
/*for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cout<<v[i][j]<<" ";
}
cout<<endl;
}*/
}
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<8;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;
}
/*cout<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cout<<w[i][j]<<" ";
}
cout<<endl;
}*/
}
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<<v[i][j]<<" "<<i<<" "<<j;
}
}
return 0;
}