Pagini recente » Borderou de evaluare (job #2964994) | Cod sursa (job #2301740)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
int di [8] = {-1, -1, -1, 1, 1, 1, 0, 0};
int dj [8] = { 0, -1, 1, 0, -1, 1, -1, 1};
bool vizitat [102][102];
int n, m, a1, a2, b1, b2, ans = 99999999, linie, coloana;
int dist1 [103][103], dist2 [103][103];
char v [102][102];
queue <pair<int, int> > q;
pair <int, int> term;
int main (){
fin >> n >> m; fin.get ();
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++){
fin.get (v [i][j]);
if (v [i][j] == 'R')a1 = i, b1 = j;
if (v [i][j] == 'J')a2 = i, b2 = j;
}
fin.get ();
}dist1 [a1][b1] = vizitat [a1][b1] = 1;
q.push ({a1, b1});
while (!q.empty ()){
term = q.front (); q.pop ();
for (int i = 0; i < 8; i ++){
int a = term.first + di [i];
int b = term.second + dj [i];
if (a >= 1 && a <= n && b >= 1 && b <= m && !vizitat [a][b] && v [a][b] == ' '){
vizitat [a][b] = 1;
dist1 [a][b] = 1 + dist1 [term.first][term.second];
q.push ({a, b});
}
}
}memset (vizitat, 0, sizeof (vizitat));
dist2 [a2][b2] = vizitat [a2][b2] = 1;
q.push ({a2, b2});
while (!q.empty ()){
term = q.front (); q.pop ();
for (int i = 0; i < 8; i ++){
int a = term.first + di [i];
int b = term.second + dj [i];
if (a >= 1 && a <= n && b >= 1 && b <= m && !vizitat [a][b] && v [a][b] == ' '){
vizitat [a][b] = 1;
dist2 [a][b] = 1 + dist2 [term.first][term.second];
q.push ({a, b});
}
}
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (dist1 [i][j] == dist2 [i][j] && dist1 [i][j] > 0 && ans > dist1 [i][j])
ans = dist1 [i][j], linie = i, coloana = j;
fout << ans << " " << linie << " " << coloana;
return 0;
}