Pagini recente » Borderou de evaluare (job #2335897) | Borderou de evaluare (job #2915555) | Borderou de evaluare (job #823520) | Borderou de evaluare (job #571409) | Cod sursa (job #2658062)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
const int NMAX = 100;
const int MMAX = 100;
bool oras[1 + NMAX][1 + MMAX];
char linie[2 + MMAX];
int romeo[1 + NMAX][1 + MMAX];
int julieta[1 + NMAX][1 + MMAX];
queue <pair<int, int>> q;
int dx[] = {-1, 0, 0, 1, 1, -1, 1,-1};
int dy[] = { 0,-1, 1, 0, 1, -1,-1, 1};
int xR, yR, xJ, yJ;
void bfs1()
{
romeo[xR][yR] = 1;
q.push(make_pair(xR, yR));
while(!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0 ; i < 8; i++)
{
int xVecin = x + dx[i];
int yVecin = y + dy[i];
if (!oras[xVecin][yVecin] && romeo[xVecin][yVecin] == 0)
{
romeo[xVecin][yVecin] = romeo[x][y] + 1;
q.push(make_pair(xVecin, yVecin));
}
}
}
}
void bfs2()
{
julieta[xJ][yJ] = 1;
q.push(make_pair(xJ, yJ));
while(!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0 ; i < 8; i++)
{
int xVecin = x + dx[i];
int yVecin = y + dy[i];
if (!oras[xVecin][yVecin] && julieta[xVecin][yVecin] == 0)
{
julieta[xVecin][yVecin] = julieta[x][y] + 1;
q.push(make_pair(xVecin, yVecin));
}
}
}
}
int main()
{
ifstream in("rj.in");
ofstream out("rj.out");
int n, m;
in >> n >> m;
in.get();
for (int i = 0; i <= n + 1; i++)
{
oras[i][0] = true;
oras[i][m + 1] = true;
}
for (int i = 0; i <= m + 1; i++)
{
oras[0][i] = true;
oras[n + 1][i] = true;
}
for (int i = 1; i <= n; i++)
{
in.getline(linie, 1 + m);
int lung = strlen(linie);
for (int j = 1; j <= lung; j++)
{
switch(linie[j - 1])
{
case 'X':
oras[i][j] = true;
break;
case 'R':
xR = i;
yR = j;
break;
case 'J':
xJ = i;
yJ = j;
}
}
}
bfs1();
bfs2();
int minim = n * m;
int iminim = -1;
int jminim = -1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (!oras[i][j] && romeo[i][j] == julieta[i][j] && romeo[i][j] != 0 && minim > romeo[i][j])
{
minim = romeo[i][j];
iminim = i;
jminim = j;
}
}
}
out << minim << ' ' << iminim << ' ' << jminim << '\n';
return 0;
}