Pagini recente » Rating Panait Alex (toisuletz) | Cod sursa (job #294968) | Cod sursa (job #1279803) | Profil mister_ady | Cod sursa (job #1655843)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");
const int DIR = 8;
const int NMAX = 100;
const int MMAX = 100;
int n, m;
pair <int, int> pozitie_r;
pair <int, int> pozitie_j;
char oras[NMAX + 1][MMAX + 1];
int drum_r[NMAX + 1][MMAX + 1];
int drum_j[NMAX + 1][MMAX + 1];
int d_i[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int d_j[] = { 0, 1, 1, 1, 0, -1, -1, -1};
int timp_sol;
vector < pair <int, int> > sol;
void citeste() {
f >> n >> m;
f.getline(oras[0], MMAX);
for (int i = 1; i <= n; i++) {
f.getline(oras[i] + 1, MMAX);
for (int j = 1; j <= m; j++) {
if (oras[i][j] == 'R') pozitie_r = make_pair(i, j);
if (oras[i][j] == 'J') pozitie_j = make_pair(i, j);
}
}
}
bool e_afara(int i, int j) {
if (i == 0 || j == 0) return true;
if (i == n + 1 || j == m + 1) return true;
return false;
}
void rezolva() {
queue < pair <char, pair <int, int> > > Q;
pair <char, pair <int, int> > p;
char personaj;
int i, j, i_urmator, j_urmator, timp;
timp_sol = n * m * 2;
p.first = 'R';
p.second = pozitie_r;
Q.push(p);
p.first = 'J';
p.second = pozitie_j;
Q.push(p);
drum_r[pozitie_r.first][pozitie_r.second] = drum_j[pozitie_j.first][pozitie_j.second] = 1;
while (!Q.empty()) {
p = Q.front();
Q.pop();
personaj = p.first;
i = p.second.first;
j = p.second.second;
if (personaj == 'R') timp = drum_r[i][j] + 1;
else timp = drum_j[i][j] + 1;
if (timp > timp_sol) continue;
for (int d = 0; d < DIR; d++) {
i_urmator = i + d_i[d];
j_urmator = j + d_j[d];
//if (personaj == 'R') cout << i_urmator << ' ' << j_urmator << ' ' << oras[i_urmator][j_urmator] << endl;
if (e_afara(i_urmator, j_urmator)) continue;
if (oras[i_urmator][j_urmator] == 'X') continue;
if(personaj == 'R') {
if (drum_r[i_urmator][j_urmator]) continue;
if (drum_j[i_urmator][j_urmator] == timp) {
if (timp_sol < timp) continue;
if (timp < timp_sol) sol.clear();
timp_sol = timp;
sol.push_back(make_pair(j_urmator, i_urmator));
}
drum_r[i_urmator][j_urmator] = timp;
}
else {
if (drum_j[i_urmator][j_urmator]) continue;
if (drum_r[i_urmator][j_urmator] == timp) {
if (timp_sol < timp) continue;
if (timp < timp_sol) sol.clear();
timp_sol = timp;
sol.push_back(make_pair(j_urmator, i_urmator));
}
drum_j[i_urmator][j_urmator] = timp;
}
p.first = personaj;
p.second.first = i_urmator;
p.second.second = j_urmator;
Q.push(p);
}
}
}
void scrie() {
pair <int, int> p;
p.first = NMAX;
p.second = MMAX;
g << timp_sol << ' ';
for (int i = 0; i < sol.size(); i++)
p = min(p, sol[i]);
g << p.second << ' ' << p.first << '\n';
}
int main() {
citeste();
rezolva();
scrie();
}