Pagini recente » Cod sursa (job #2449742) | Cod sursa (job #1119497) | Cod sursa (job #2111214) | Cod sursa (job #2184667) | Cod sursa (job #552857)
Cod sursa(job #552857)
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#include <string>
using namespace std;
#define maxN 105
#define PB push_back
#define PF pop_front
int N, M;
bool a[maxN][maxN];
int ll[] = {-1, -1, 0, 1, 1, 1, 0, -1}, col[] = {0, -1, -1, -1, 0, 1, 1, 1};
int R[maxN][maxN], J[maxN][maxN];
int x1, x2, y11, y2;
void bf (int x1, int y1, int who[maxN][maxN])
{
deque < int > coada[3];
coada[1].PB(x1);
coada[2].PB(y1);
memset (who, -1, sizeof(who));
who[x1][y1] = 1;
for ( ; coada[1].size(); )
{
int x = coada[1][0], y = coada[2][0];
for (int i = 0; i < 8; ++ i)
{
if (x + ll[i] < 1 || x + ll[i] > N)
continue;
if (y + col[i] < 1 || y + col[i] > M)
continue;
int xp = x + ll[i], yp = y + col[i];
if (a[xp][yp])
continue;
if (who[xp][yp] != - 1)
continue;
coada[1].PB(xp);
coada[2].PB(yp);
who[xp][yp] = who[x][y] + 1;
}
coada[1].PF();
coada[2].PF();
}
}
int main()
{
ifstream f("rj.in");
ofstream g("rj.out");
f >> N >> M;
memset (R, -1, sizeof(R));
memset (J, -1, sizeof(J));
for (int i = 1; i <= N; ++ i)
{
f.get();
for (int j = 1; j <= M; ++ j)
{
char c;
f.get(c);
if (c == 'X')
a[i][j] = true;
if (c == 'R')
{
R[i][j] = 1;
x1 = i;
y11 = j;
}
if (c == 'J')
{
J[i][j] = 1;
x2 = i;
y2 = j;
}
}
}
bf (x1, y11, R);
bf (x2, y2, J);
int minim = maxN * maxN, pozi = 0, pozj = 0;
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= M; ++ j)
if (R[i][j] == J[i][j] && minim > R[i][j] && R[i][j] > 0)
{
minim = R[i][j];
pozi = i;
pozj = j;
}
g << minim << " ";
g << pozi << " " << pozj;
f.close();
g.close();
return 0;
}