Pagini recente » Cod sursa (job #1031213) | Cod sursa (job #1309727) | Cod sursa (job #2644907) | Cod sursa (job #2229330) | Cod sursa (job #2097513)
#include <bits/stdc++.h>
#define in "rj.in"
#define out "rj.out"
#define oo 1000000
using namespace std;
ifstream fin(in);
ofstream fout(out);
int n,m,xr,yr,xj,yj;
int dr[105][105];
int dj[105][105];
char a[105][105];
int dx[]={0,0,-1,1,-1,1,-1,1};
int dy[]={-1,1,0,0,-1,1,1,-1};
queue <pair<int,int> > q;
void Citire()
{
int i,j;
fin >> n >> m;
fin.get();
for (i = 1; i <= n; i++)
{
fin.getline(a[i]+1,105);
for (j = 1; j <= m; j++)
if (a[i][j] == 'R')
{
xr = i;
yr = j;
}
else if (a[i][j] == 'J')
{
xj = i;
yj = j;
}
}
}
void Bordare()
{
int i;
for (i = 0;i <= m + 1; i++) a[0][i] = a[n+1][i] = 'X';
for (i = 0;i <= n + 1; i++) a[i][0] = a[i][m+1] = 'X';
}
void Init()
{
int i,j;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
dj[i][j] = dr[i][j] = oo;
}
void Lee_R()
{
int i,j,x,y,k;
q.push({xr,yr});
dr[xr][yr] = 1;
while(!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for (k = 0; k < 8; k++)
{
x = i + dx[k];
y = j + dy[k];
if (dr[x][y] > dr[i][j] + 1 && a[x][y] != 'X')
{
dr[x][y] = dr[i][j] + 1;
q.push({x,y});
}
}
}
}
void Lee_J()
{
int i,j,x,y,k;
q.push({xj,yj});
dj[xj][yj] = 1;
while(!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for (k = 0; k < 8; k++)
{
x = i + dx[k];
y = j + dy[k];
if (dj[x][y] > dj[i][j] + 1 && a[x][y] != 'X')
{
dj[x][y] = dj[i][j] + 1;
q.push({x,y});
}
}
}
}
void Intalnire()
{
int i,j,mini,poz1,poz2;
mini = oo;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
if(dr[i][j] == dj[i][j] && mini > dr[i][j])
{
mini = dr[i][j];
poz1 = i;
poz2 = j;
}
fout << mini << " " << poz1 << " " << poz2 << "\n";
}
int main()
{
Citire();
Bordare();
Init();
Lee_R();
Lee_J();
Intalnire();
fin.close();
fout.close();
return 0;
}