Pagini recente » Cod sursa (job #108123) | Cod sursa (job #1089462) | Cod sursa (job #1571095) | Cod sursa (job #2587653) | Cod sursa (job #2604389)
#include <iostream>
#include <fstream>
#include <queue>
#define N 110
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n, m;
int R[N][N], lr, cr; ///matrice care retine lungimile distantelor parcurse de Romeo
int J[N][N], lj, cj; ///matrice care retine lungimile distantelor parcurse de Julieta
int dl[]= {-1,0,1,0,-1,1,1,-1};
int dc[]= {0,1,0,-1,1,1,-1,-1};
void Read()
{
int i, j;
char s[101];
fin >> n >> m;
fin.get();
for(int i=1; i<=n; i++)
{
fin.getline(s,101);
for(j=0; s[j]; j++)
if(s[j] == ' ')
R[i][j+1] = J[i][j+1] = 0;
else
if(s[j] == 'R')
lr=i, cr=j+1, R[i][j+1] = J[i][j+1] = 0;
else
if(s[j] == 'J')
lj=i, cj=j+1, R[i][j+1] = J[i][j+1] = 0;
else
R[i][j+1] = J[i][j+1] = -1;
}
}
void Bordare()
{
for(int j=0; j<=m+1; j++)
R[0][j] = R[n+1][j] = J[0][j] = J[n+1][j] = -1;
for(int i=0; i<=n+1; i++)
R[i][0] = R[i][m+1] = J[i][0] = J[i][m+1] = -1;
}
void LeeR()
{
int l, c, lv, cv, k;
queue <int> L, C;
L.push(lr);
C.push(cr);
while(!L.empty())
{
l = L.front();
L.pop();
c = C.front();
C.pop();
for(k=0; k<8; k++)
{
lv = dl[k] + l;
cv = dc[k] + c;
if(R[lv][cv] == 0)
{
R[lv][cv] = R[l][c] + 1;
L.push(lv);
C.push(cv);
}
}
}
}
void LeeJ()
{
int l, c, lv, cv, k;
queue <int> L, C;
L.push(lj);
C.push(cj);
while(!L.empty())
{
l = L.front();
L.pop();
c = C.front();
C.pop();
for(k=0; k<8; k++)
{
lv = dl[k] + l;
cv = dc[k] + c;
if(J[lv][cv] == 0)
{
J[lv][cv] = J[l][c] + 1;
L.push(lv);
C.push(cv);
}
}
}
}
void Solve()
{
int lmin, cmin, mini = 20000;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(R[i][j] == J[i][j] && R[i][j] != -1 && R[i][j] != 0)
if(R[i][j] < mini)
{
lmin = i;
cmin = j;
mini = R[i][j];
}
fout << mini+1 <<" ";
fout << lmin << " " << cmin;
}
int main()
{
Read();
Bordare();
LeeR();
LeeJ();
Solve();
return 0;
}
/*
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
fout << R[i][j] << " ";
fout << "\n";
}
*/