Pagini recente » Cod sursa (job #1409377) | Cod sursa (job #1693538) | Cod sursa (job #587149) | Cod sursa (job #2570603) | Cod sursa (job #2186414)
#include <bits/stdc++.h>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int n, m, distRomeo[110][110], distJulieta[110][110], minim = 1e9;
bool a[110][110], viz[110][110];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
void BFSRomeo(pair< int, int > startNode) {
queue< pair< int, int > > q; q.push(startNode);
memset(viz, 0, sizeof(viz));
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second; q.pop();
viz[x][y] = true;
for(int k = 0; k < 8; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 1 || ny < 1 || nx > n || ny > m || viz[nx][ny] == 1 || a[nx][ny] == 0) {
continue;
}
distRomeo[nx][ny] = distRomeo[x][y] + 1;
q.push(make_pair(nx, ny));
viz[nx][ny] = 1;
}
}
}
void BFSJulieta(pair< int, int > startNode) {
queue< pair< int, int > > q; q.push(startNode);
memset(viz, 0, sizeof(viz));
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second; q.pop();
viz[x][y] = true;
for(int k = 0; k < 8; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 1 || ny < 1 || nx > n || ny > m || viz[nx][ny] == 1 || a[nx][ny] == 0) {
continue;
}
distJulieta[nx][ny] = distJulieta[x][y] + 1;
q.push(make_pair(nx, ny));
viz[nx][ny] = 1;
}
}
}
int main() {
ios::sync_with_stdio(false); in.tie(0); out.tie(0);
in >> n >> m;
in.get();
pair< int, int > startRomeo, startJulieta;
for(int i = 1; i <= n; ++i) {
char line[110]; in.getline(line, 110);
for(int j = 0; line[j]; ++j) {
if(line[j] == 'R') {
a[i][j + 1] = 0;
startRomeo = make_pair(i, j + 1);
continue;
}
if(line[j] == 'J') {
a[i][j + 1] = 0;
startJulieta = make_pair(i, j + 1);
continue;
}
if(line[j] == ' ') {
a[i][j + 1] = 1;
} else {
a[i][j + 1] = 0;
}
}
}
BFSRomeo(startRomeo);
BFSJulieta(startJulieta);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(distRomeo[i][j] == distJulieta[i][j] && distRomeo[i][j] && distRomeo[i][j] < minim) {
minim = distRomeo[i][j];
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(distRomeo[i][j] == distJulieta[i][j] && distRomeo[i][j] == minim) {
out << minim + 1 << " " << i << " " << j << '\n';
j = m + 1;
i = n + 1;
}
}
}
in.close(); out.close();
return 0;
}