Pagini recente » Cod sursa (job #2619202) | Cod sursa (job #983294) | Cod sursa (job #2447348) | Cod sursa (job #1637920) | Cod sursa (job #2665338)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
int n, m, i, j, k, x, y, rx, ry, jx, jy, min1, px[] = {-1, -1, -1, 0, 1, 1, 1, 0}, py[] = {-1, 0, 1, 1, 1, 0, -1, -1}, romeo[105][105], julieta[105][105];
char h[105][105];
int main() {
ifstream f("rj.in");
ofstream g("rj.out");
queue<pair<int, int>> poz;
f >> n >> m;
f.get();
for(i = 0; i < n; i++) {
f.getline(h[i], 105);
k = strlen(h[i]);
while(k < m) {
h[i][k] = ' ';
k++;
}
h[i][m] = '\0';
for(j = 0; j < m; j++) {
romeo[i][j] = julieta[i][j] = 10005;
if(h[i][j] == 'R') {
rx = i;
ry = j;
}
if(h[i][j] == 'J') {
jx = i;
jy = j;
}
}
}
f.close();
poz.emplace(rx, ry);
romeo[rx][ry] = 1;
while(!poz.empty()) {
i = poz.front().first;
j = poz.front().second;
poz.pop();
for(k = 0; k < 8; k++)
if(0 <= i + px[k] && i + px[k] < n && 0 <= j + py[k] && j + py[k] < m && h[i + px[k]][j + py[k]] != 'X' && romeo[i][j] + 1 < romeo[i + px[k]][j + py[k]]) {
romeo[i + px[k]][j + py[k]] = romeo[i][j] + 1;
poz.emplace(i + px[k], j + py[k]);
}
}
poz.emplace(jx, jy);
julieta[jx][jy] = 1;
while(!poz.empty()) {
i = poz.front().first;
j = poz.front().second;
poz.pop();
for(k = 0; k < 8; k++)
if(0 <= i + px[k] && i + px[k] < n && 0 <= j + py[k] && j + py[k] < m && h[i + px[k]][j + py[k]] != 'X' && julieta[i][j] + 1 < julieta[i + px[k]][j + py[k]]) {
julieta[i + px[k]][j + py[k]] = julieta[i][j] + 1;
poz.emplace(i + px[k], j + py[k]);
}
}
min1 = 10005;
x = y = -1;
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
if(romeo[i][j] == julieta[i][j] && romeo[i][j] < min1) {
min1 = romeo[i][j];
x = i + 1;
y = j + 1;
}
g << min1 << ' ' << x << ' ' << y << '\n';
g.close();
return 0;
}