Pagini recente » Cod sursa (job #1298689) | Cod sursa (job #3281812) | Cod sursa (job #1675249) | Cod sursa (job #1955031) | Cod sursa (job #1618492)
#include <fstream>
#include <deque>
#include <string>
#define L 105
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int e[L][L], n, m, nrPasi, e2[L][L];
bool d[L][L], seen1[L][L], seen2[L][L], pozGasit[L][L];
int dl[4] = {-1, 0, 0, 1};
int dc[4] = {0, -1, 1, 0};
string s;
struct P{
int l, c;
}a, b, p, v;
deque <P > C;
bool check(int i, int j){
if (i >= 1 && i <= n && j >= 1 && j <= m && seen1[i][j] == 0 && d[i][j] == 0) return 1;
return 0;
}
bool check2(int i, int j){
if (i >= 1 && i <= n && j >= 1 && j <= m && seen2[i][j] == 0 && d[i][j] == 0) return 1;
return 0;
}
int main()
{
fin >> n >> m;
fin.get();
for (int i = 1; i <= n; i++){
getline(fin, s);
for (int j = 0; j < s.size(); j++){
if (s[j] == 'R'){
d[i][j + 1] = 0;
a.l = i; a.c = j + 1;
}
if (s[j] == 'X')
d[i][j + 1] = 1;
if (s[j] == ' ')
d[i][j + 1] = 0;
if (s[j] == 'J'){
d[i][j + 1] = 0;
b.l = i; b.c = j + 1;
}
}
}
/*for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++)
fout << d[i][j] << " ";
fout << endl;
}*/
C.push_back(a);
while (!C.empty()){
p = C.front();
C.pop_front();
for (int i = 0; i <= 3; i++){
v.l = p.l + dl[i];
v.c = p.c + dc[i];
if (check(v.l, v.c)){
seen1[v.l][v.c] = 1;
e[v.l][v.c] = e[p.l][p.c] + 1;
C.push_back(v);
}
}
if (seen1[b.l][b.c] == 1) break;
}
//fout << e[b.l][b.c] << endl;
if (e[b.l][b.c] % 2 == 0) nrPasi = e[b.l][b.c] / 2;
else nrPasi = e[b.l][b.c] / 2 + 1;
C.clear();
C.push_back(b);
e2[b.l][b.c] = 0;
while (!C.empty()){
p = C.front();
C.pop_front();
for (int i = 0; i <= 3; i++){
v.l = p.l + dl[i];
v.c = p.c + dc[i];
if (check2(v.l, v.c)){
seen2[v.l][v.c] = 1;
e2[v.l][v.c] = e2[p.l][p.c] + 1;
C.push_back(v);
if (e2[v.l][v.c] == nrPasi)
pozGasit[v.l][v.c] = 1;
}
}
if (seen2[a.l][a.c] == 1) break;
}
fout << nrPasi << " ";
bool ok = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++)
if (pozGasit[i][j] == 1){
fout << i << " " << j;
ok = 1;
break;
}
if (ok == 1) break;
}
return 0;
}