Cod sursa(job #2978362)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 13 februarie 2023 18:21:21
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#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, 0, 1, 0}, dy = {0, 1, 0, -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] = 0;

    int x, y, xx, yy;
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for (int i = 0 ; i < 4 ; ++ 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;
}