Cod sursa(job #2524682)

Utilizator Rares5000Baciu Rares Rares5000 Data 16 ianuarie 2020 00:14:43
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <bits/stdc++.h>
#define oo 2000000000

using namespace std;

char s[102];
int a[102][102];
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
int n, m, d[105][105], dist[105][105], xj, yj, xr, yr;
queue < pair<int, int> >q;

inline bool Inside(int i, int j)
{
    return i <= n && i >= 1 && j <= m && j >= 1;
}

ifstream fin("rj.in");
ofstream fout("rj.out");

void Leeromeo()
{
    int i, j, x, y, k;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            d[i][j] = oo;
    d[xr][yr] = 1;
    q.push({xr, yr});
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for(k = 0; k < 8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if(Inside(x, y) && a[x][y] == 0 && d[x][y] > d[i][j] + 1)
            {
                d[x][y] = d[i][j] + 1;
                q.push({x, y});
            }
        }
    }
}

void Leejulieta()
{
    int i, j, x, y, k;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            dist[i][j] = oo;
    dist[xj][yj] = 1;
    q.push({xj, yj});
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for(k = 0; k < 8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if(Inside(x, y) && a[x][y] == 0 && dist[x][y] > dist[i][j] + 1)
            {
                dist[x][y] = dist[i][j] + 1;
                q.push({x, y});
            }
        }
    }
}

int main()
{
    int i, j, minim = oo, minimi, minimj;
    fin >> n >> m;
    fin.get();
    for(i = 1; i <= n; i++)
    {
        fin.getline(s + 1, 102);
        for(j = 1; j <= m; j++)
        {
            if(s[j] == ' ')
                a[i][j] = 0;
            else if(s[j] == 'X')
                a[i][j] = 1;
            else if(s[j] == 'R')
            {
                xr = i;
                yr = j;
            }
            else if(s[j] == 'J')
            {
                xj = i;
                yj = j;
            }
        }
    }
    Leeromeo();
    Leejulieta();
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            if(d[i][j] != oo && dist[i][j] != oo && d[i][j] == dist[i][j])
                if(d[i][j] < minim)
                {
                    minim = d[i][j];
                    minimi = i;
                    minimj = j;
                }
    fout << minim << " " << minimi << " " << minimj;
    return 0;
}