Pagini recente » Cod sursa (job #2021793) | Cod sursa (job #393346) | Cod sursa (job #835189) | Cod sursa (job #1593053) | Cod sursa (job #2206590)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct punct
{
int abs,ord;
};
bool Check(int x,int y,int n,int m)
{
if(x<1) return false;
if(y<1) return false;
if(x>=n) return false;
if(y>=m) return false;
return true;
}
void ConstruiesteMatriceDistante(const punct& start, const vector<vector<bool> >& ma,vector<vector<int> >& dist)
{
int dx[]= {-1,-1,-1,0,1,1,1,0},dy[]= {-1,0,1,1,1,0,-1,-1};
queue<punct > coada;
vector<vector<bool> > viz;
dist.resize(ma.size());
viz.resize(ma.size());
for(int i=1; i<dist.size(); ++i)
{
dist[i].resize(ma[i].size(),-1);
viz[i].resize(ma[i].size(),false);
}
coada.push(start);
viz[start.abs][start.ord]=true;
dist[start.abs][start.ord]=1;
while(!coada.empty())
{
punct curr=coada.front();
coada.pop();
for(int i=0; i<8; ++i)
if(Check(curr.abs+dx[i],curr.ord+dy[i],ma.size(),ma[1].size()) && !viz[curr.abs+dx[i]][curr.ord+dy[i]] && ma[curr.abs+dx[i]][curr.ord+dy[i]]==true)
{
dist[curr.abs+dx[i]][curr.ord+dy[i]]=dist[curr.abs][curr.ord]+1;
viz[curr.abs+dx[i]][curr.ord+dy[i]]=true;
coada.push({curr.abs+dx[i],curr.ord+dy[i]});
}
}
}
int main()
{
ifstream fin("rj.in");
ofstream fout("rj.out");
punct romeo,julieta;
int n,m;char s[102];
vector<vector<bool> > mat;
vector<vector<int> > dist1,dist2;
fin>>n>>m;
mat.resize(n+1);
fin.get();
for(int i=1; i<=n; ++i)
{
mat[i].resize(m+1);
fin.getline(s,100);
for(int j=1; j<=m; ++j)
{
if(s[j-1]=='R')
{
romeo.abs=i;
romeo.ord=j;
mat[i][j]=true;
continue;
}
if(s[j-1]=='J')
{
julieta.abs=i;
julieta.ord=j;
mat[i][j]=true;
continue;
}
if(s[j-1]==' ')
{
mat[i][j]=true;
continue;
}
mat[i][j]=false;
}
}
ConstruiesteMatriceDistante(romeo,mat,dist1);
/*for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
fout<<dist1[i][j]<<' ';
fout<<'\n';
}*/
ConstruiesteMatriceDistante(julieta,mat,dist2);
/*for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
fout<<dist2[i][j]<<' ';
fout<<'\n';
}*/
for(int i=1;i<mat.size();++i)
for(int j=1;j<mat[i].size();++j)
if(dist1[i][j]==dist2[i][j] && dist1[i][j]!=-1)
{fout<<dist1[i][j]<<' '<<i<<' '<<j; break;}
return 0;
}