Pagini recente » Cod sursa (job #1957303) | Cod sursa (job #1498441) | Cod sursa (job #2912720) | Cod sursa (job #2946138) | Cod sursa (job #2282475)
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int Dim = 105, Inf = 0x3f3f3f3f;
const int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
const int dj[] = {0, 1, 0, -1, -1, 1, -1, 1};
struct Cel {
int i, j;
};
char L[Dim][Dim];
int rc[Dim][Dim], jc[Dim][Dim];
int n, m, ip, jp ,is, js;
int soli, solj, tmin = Dim * Dim;
bool nw;
void ReadMatrix();
void LeeRomeo();
void LeeJulieta();
bool Ok(int i, int j);
int main()
{
ReadMatrix();
LeeRomeo();
LeeJulieta();
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if((rc[i][j] == jc[i][j] && rc[soli][solj] > rc[i][j] && rc[i][j] != Inf) || (nw == false))
soli = i, solj = j, nw = true;
}
}
fout << rc[soli][solj] + 1 << ' ' << soli << ' ' << solj << '\n';
}
void LeeRomeo()
{
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
rc[i][j] = Inf;
queue<Cel> Q;
rc[ip][jp] = 0;
Q.push({ip, jp});
int i, j, iv, jv;
while (!Q.empty())
{
i = Q.front().i;
j = Q.front().j;
Q.pop();
for (int d = 0; d < 8; ++d)
{
iv = i + di[d];
jv = j + dj[d];
if (Ok(iv, jv) && rc[iv][jv] > rc[i][j] + 1)
{
rc[iv][jv] = rc[i][j] + 1;
Q.push({iv, jv});
}
}
}
}
void LeeJulieta()
{
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
jc[i][j] = Inf;
queue<Cel> Q;
jc[is][js] = 0;
Q.push({is, js});
int i, j, iv, jv;
while (!Q.empty())
{
i = Q.front().i;
j = Q.front().j;
Q.pop();
for (int d = 0; d < 8; ++d)
{
iv = i + di[d];
jv = j + dj[d];
if (Ok(iv, jv) && jc[iv][jv] > jc[i][j] + 1)
{
jc[iv][jv] = jc[i][j] + 1;
Q.push({iv, jv});
}
}
}
}
bool Ok(int i, int j)
{
if (i < 1 || i > n || j < 1 || j > m)
return false;
if (L[i][j] == 'X')
return false;
return true;
}
void ReadMatrix()
{
fin >> n >> m;
fin.get();
for(int i = 1; i <= n; ++i)
{
fin.getline((L[i] + 1), Dim + 1);
for(int j = 1; j <= m; ++j)
{
if(L[i][j] == 'R')ip = i, jp = j;
if(L[i][j] == 'J')is = i, js = j;
}
}
}