Pagini recente » Cod sursa (job #1803231) | Cod sursa (job #104510) | Cod sursa (job #2673626) | Cod sursa (job #611337) | Cod sursa (job #2588392)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int nmax=105;
const int mmax=105;
int dx[8]={-1,-1,1,1,-1,0,1,0};
int dy[8]={-1,1,1,-1,0,1,0,-1};
int n,m,a[nmax][mmax],mnR[nmax][mmax],mnJ[nmax][mmax];
int ir,jr,ij,jj;
struct cell
{
int x,y;
};
void read_data()
{
char b[mmax];
fin>>n>>m;
fin.get();
for(int i=1;i<=n;i++)
{
fin.getline(b,m+2);
for(int j=0;j<m;j++)
if(b[j]=='R')
{
a[i][j+1]=-2;
ir=i,jr=j+1;
}
else if(b[j]=='J')
{
a[i][j+1]=-2;
ij=i,jj=j+1;
}
else if(b[j]=='X')
a[i][j+1]=-1;
}
}
bool okei(int lin,int col)
{
if(lin>=1 && lin<=n && col>=1 && col<=m)
return true;
return false;
}
void bfs_algR()
{
deque <cell> d;
d.push_back({ir,jr});
mnR[ir][jr]=1;
while(!d.empty())
{
int lin=d.front().x;
int col=d.front().y;
d.pop_front();
for(int k=0;k<8;k++)
{
int ll=lin+dx[k];
int cc=col+dy[k];
if(okei(ll,cc) && (a[ll][cc]==0))
if(mnR[ll][cc]==0)
{
mnR[ll][cc]=mnR[lin][col]+1;
d.push_back({ll,cc});
}
}
}
}
void bfs_algJ()
{
deque <cell> d;
d.push_back({ij,jj});
mnJ[ij][jj]=1;
while(!d.empty())
{
int lin=d.front().x;
int col=d.front().y;
d.pop_front();
for(int k=0;k<8;k++)
{
int ll=lin+dx[k];
int cc=col+dy[k];
if(okei(ll,cc) && (a[ll][cc]==0))
if(mnJ[ll][cc]==0)
{
mnJ[ll][cc]=mnJ[lin][col]+1;
d.push_back({ll,cc});
}
}
}
}
void solve()
{
bfs_algR();
bfs_algJ();
int tmin=nmax*mmax,x,y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mnR[i][j]==mnJ[i][j] && mnR[i][j]<tmin && mnR[i][j]>0)
{
tmin=mnR[i][j];
x=i;
y=j;
}
fout<<tmin<<" "<<x<<" "<<y;
}
int main()
{
read_data();
solve();
return 0;
}