Pagini recente » Cod sursa (job #2729444) | Cod sursa (job #2446279) | Cod sursa (job #3129216) | Cod sursa (job #2556003) | Cod sursa (job #2206008)
#include <bits/stdc++.h>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
bool harta[110][110], viz[110][110];
int n, m, dRomeo[110][110], dJulieta[110][110], minim = 1e9;
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 > start) {
queue< pair< int, int > > q; q.push(start);
memset(viz, false, sizeof(viz));
viz[start.first][start.second] = true;
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
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] || harta[nx][ny] == 0) {
continue;
}
dRomeo[nx][ny] = dRomeo[x][y] + 1;
viz[nx][ny] = true;
q.push({nx, ny});
}
}
}
void BFSJulieta(pair< int, int > start) {
queue< pair< int, int > > q; q.push(start);
memset(viz, false, sizeof(viz));
viz[start.first][start.second] = true;
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
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] || harta[nx][ny] == 0) {
continue;
}
dJulieta[nx][ny] = dJulieta[x][y] + 1;
viz[nx][ny] = true;
q.push({nx, ny});
}
}
}
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') {
harta[i][j + 1] = 0;
startRomeo = make_pair(i, j + 1);
continue;
}
if(line[j] == 'J') {
harta[i][j + 1] = 0;
startJulieta = make_pair(i, j + 1);
continue;
}
if(line[j] == ' ') {
harta[i][j + 1] = 1;
} else {
harta[i][j + 1] = 0;
}
}
}
BFSRomeo(startRomeo);
BFSJulieta(startJulieta);
int x = 0, y = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(dRomeo[i][j] == dJulieta[i][j] && dRomeo[i][j] && dRomeo[i][j] < minim) {
minim = dRomeo[i][j];
x = i; y = j;
}
}
}
out << minim + 1 << " " << x << " " << y << "\n";
in.close(); out.close();
return 0;
}