Pagini recente » Cod sursa (job #3160366) | Cod sursa (job #812729) | Cod sursa (job #2056352) | Cod sursa (job #2035802) | Cod sursa (job #3160540)
#include <fstream>
#include <queue>
using namespace std;
queue < pair<int, int> > R;
queue < pair<int, int> > J;
pair <int, int> startrom;
pair <int, int> startjul;
int romeo[102][102], julieta[103][103];
int n, m;
int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
void bordare(){
for(int i = 0; i <= n + 1; i++) {
romeo[i][0] = -1;
romeo[i][m + 1] = -1;
julieta[i][0] = -1;
julieta[i][m + 1] = -1;
}
for(int j = 1; j <= m; j++) {
romeo[0][j] = -1;
romeo[n + 1][j] = -1;
julieta[0][j] = -1;
julieta[n + 1][j] = -1;
}
}
void citire() {
char c;
ifstream fin("rj.in");
fin >> n >> m;
fin.get(c);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++){
fin.get(c);
if(c == 'R') {
startrom.first = i;
startrom.second = j;
julieta[i][j] = 0;
}
if(c == 'J') {
startjul.first = i;
startjul.second = j;
romeo[i][j] = 0;
}
if(c == ' ') {
romeo[i][j] = 0;
julieta[i][j] = 0;
}
if(c == 'X') {
romeo[i][j] = -1;
julieta[i][j] = -1;
}
}
fin.get(c);
}
}
void leer() {
R.push(startrom);
romeo[startrom.first][startrom.second] = 1;
while(!R.empty()) {
pair<int, int> current = R.front();
R.pop();
for(int k = 0; k < 8; k++) {
int pi = current.first + di[k];
int pj = current.second + dj[k];
if(romeo[pi][pj] == 0) {
romeo[pi][pj] = romeo[current.first][current.second] + 1;
R.push({pi, pj});
}
}
}
}
void leej() {
J.push(startjul);
julieta[startjul.first][startjul.second] = 1;
while(!J.empty()) {
pair<int, int> current = J.front();
J.pop();
for(int k = 0; k < 8; k++) {
int pi = current.first + di[k];
int pj = current.second + dj[k];
if(julieta[pi][pj] == 0) {
julieta[pi][pj] = julieta[current.first][current.second] + 1;
J.push({pi, pj});
}
}
}
}
void gasire() {
int min_path = 200000000;
int i_i = -1, j_j = -1, pasi = -1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if(romeo[i][j] == julieta[i][j] && romeo[i][j] < min_path && romeo[i][j] != 0 && romeo[i][j]!=-1) {
pasi = romeo[i][j];
min_path = pasi;
i_i = i;
j_j = j;
}
}
ofstream fout("rj.out");
if(i_i != -1 && j_j != -1 && pasi != -1) {
fout << pasi << " " << i_i << " " << j_j;
}
}
int main() {
citire();
bordare();
leer();
leej();
gasire();
return 0;
}