Pagini recente » Cod sursa (job #1180519) | Cod sursa (job #2423087) | Cod sursa (job #1694530) | Cod sursa (job #2335091) | Cod sursa (job #2978366)
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;
using namespace std;
const int NMAX = 105;
const int INF = 1e8;
/*******************************/
// INPUT / OUTPUT
ifstream f("rj.in");
ofstream g("rj.out");
/*******************************/
/// GLOBAL DECLARATIONS
int N, M;
int rx, ry, jx, jy, ansx, ansy, min_dist = INF;
int dist[2][NMAX][NMAX];
bool grid[NMAX][NMAX], vis[NMAX][NMAX];
vector <int> dx = {-1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, 1, 1, 1, 0, -1, -1, -1};
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
f >> N >> M;
string line;
getline(f, line);
for (int i = 1 ; i <= N ; ++ i)
{
getline(f, line);
for (int j = 0 ; j < M ; ++ j)
{
grid[i][j + 1] = 0;
if (line[j] == 'X') grid[i][j + 1] = 1;
if (line[j] == 'R') rx = i, ry = j + 1;
if (line[j] == 'J') jx = i, jy = j + 1;
dist[0][i][j + 1] = dist[1][i][j + 1] = INF;
}
}
}
///-------------------------------------
bool ok(ci &x, ci &y)
{
return (1 <= x && x <= N && 1 <= y && y <= M);
}
///-------------------------------------
inline void bfs(bool tip, int startX, int startY)
{
queue <pii> q;
memset(vis, false, sizeof(vis));
q.push({startX, startY});
vis[startX][startY] = true;
dist[tip][startX][startY] = 1;
int x, y, xx, yy;
while (!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop();
for (int i = 0 ; i < 8 ; ++ i)
{
xx = x + dx[i];
yy = y + dy[i];
if (ok(xx, yy) && !grid[xx][yy] && !vis[xx][yy])
{
vis[xx][yy] = true;
dist[tip][xx][yy] = dist[tip][x][y] + 1;
q.push({xx, yy});
}
}
}
}
///-------------------------------------
inline void Solution()
{
bfs(0, rx, ry);
bfs(1, jx, jy);
for (int i = 1 ; i <= N ; ++ i)
{
for (int j = 1 ; j <= M ; ++ j)
{
if (grid[i][j] || (dist[0][i][j] != dist[1][i][j])) continue;
if (min_dist > dist[0][i][j])
{
min_dist = dist[0][i][j];
ansx = i, ansy = j;
}
}
}
}
///-------------------------------------
inline void Output()
{
g << min_dist << " " << ansx << " " << ansy;
}
///-------------------------------------
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ReadInput();
Solution();
Output();
return 0;
}