Pagini recente » Cod sursa (job #1450092) | Cod sursa (job #2664933) | Cod sursa (job #754562) | Cod sursa (job #1764165) | Cod sursa (job #2865155)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
typedef pair < int, int > PII;
const int NMAX = 103;
struct str
{
int x;
int y;
int val;
};
int N, M;
int v[NMAX][NMAX];
int d1[NMAX][NMAX], d2[NMAX][NMAX];
bool sel[NMAX][NMAX];
PII romeo, julieta;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
static inline void Reset()
{
for(int i = 1; i <= N; ++ i)
for(int j = 1; j <= M; ++j)
sel[i][j] = false;
return;
}
static inline bool Inbounds(PII a)
{
return (1 <= a.first && a.first <= N && 1 <= a.second && a.second <= M);
}
static inline void Lee1(PII start)
{
Reset();
queue < PII > q;
q.push(start);
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 8; ++i) {
int xx = x + dx[i];
int yy = y + dy[i];
if(Inbounds({xx, yy}) && (!sel[xx][yy] || (sel[xx][yy] && d1[xx][yy] > d1[x][y] + 1)) && v[xx][yy] != -1) {
q.push({xx, yy});
sel[xx][yy] = true;
d1[xx][yy] = d1[x][y] + 1;
}
}
}
return;
}
static inline void Lee2(PII start)
{
Reset();
queue < PII > q;
q.push(start);
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 8; ++i) {
int xx = x + dx[i];
int yy = y + dy[i];
if(Inbounds({xx, yy}) && (!sel[xx][yy] || (sel[xx][yy] && d2[xx][yy] > d2[x][y] + 1)) && v[xx][yy] != -1) {
q.push({xx, yy});
sel[xx][yy] = true;
d2[xx][yy] = d2[x][y] + 1;
}
}
}
return;
}
static inline void Read()
{
fin >> N >> M;
char x;
fin.get();
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= M; ++j) {
fin.get(x);
if(x == 'R')
romeo = {i, j};
if(x == 'J')
julieta = {i, j};
if(x == 'X')
v[i][j] = -1;
}
fin.get();
}
return;
}
static inline str mymin(str a, str b)
{
return (a.val < b.val ? a : b);
}
int main()
{
Read();
Lee1(romeo);
Lee2(julieta);
str ans = {0, 0, 100000000};
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
if(d1[i][j] == d2[i][j] && d1[i][j] != 0)
ans = mymin(ans, {i, j, d1[i][j]});
fout << ans.val + 1 << " " << ans.x << " " << ans.y << '\n';
return 0;
}