Mai intai trebuie sa te autentifici.
Cod sursa(job #2762665)
Utilizator | Data | 9 iulie 2021 11:11:03 | |
---|---|---|---|
Problema | Rj | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 2.05 kb |
#include <fstream>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
char s[101];
int n, m;
int a[101][101];
int romeo[101][101];
int juliet[101][101];
int isr, jsr;
int isj, jsj;
int Min, iintalnire, jintalnire;
void read() {
int i, j;
ifstream f("rj.in");
f >> n >> m; f.get();
for (i = 1; i <= n; i++) {
f.getline(s, 101);
for (j = 0; j < m; j++)
if (s[j] == 'R')
isr = i, jsr = j + 1;
else if (s[j] == 'J')
isj = i, jsj = j + 1;
else if (s[j] == 'X')
a[i][j + 1] = 1;
}
}
const int di[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dj[] = {0, 1, 0, -1, -1, 1, -1, 1};
queue<pair<int, int>> Q;
bool inside(int i, int j) {
if (i >= 1 && j >= 1 && i <= n && j <= m)
return 1;
return 0;
}
void lee(int istart, int jstart, int mat[][101]) {
int i, j, inou, jnou, k;
mat[istart][jstart] = 1;
Q.push({istart, jstart});
while (!Q.empty()) {
i = Q.front().first, j = Q.front().second;
for (k = 0; k < 8; k++) {
inou = i + di[k], jnou = j + dj[k];
if (inside(inou, jnou) && a[inou][jnou] == 0 && mat[inou][jnou] == 0) {
Q.push({inou, jnou});
mat[inou][jnou] = mat[i][j] + 1;
}
}
Q.pop();
}
}
void solve() {
// un lee pentru romeo
lee(isr, jsr, romeo);
// un lee pentru juliet
lee(isj, jsj, juliet);
// punctul de intalnire
int i, j;
Min = 1e9;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
if (romeo[i][j] > 0 && juliet[i][j] > 0 && romeo[i][j] == juliet[i][j] && romeo[i][j] < Min) {
Min = romeo[i][j];
iintalnire = i, jintalnire = j;
}
}
void output() {
ofstream g("rj.out");
g << Min << ' ' << iintalnire << ' ' << jintalnire;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}