Cod sursa(job #2557210)

Utilizator FrostfireMagirescu Tudor Frostfire Data 25 februarie 2020 17:13:33
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
#define NMAX 100
#define inf 2000000000

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int n, m, ans = inf, sol[3][NMAX+10][NMAX+10];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
pair <int, int> poz[3], coord;
bool viz[NMAX+10][NMAX+10];
queue <pair <int, int> > Q;
char a[NMAX+10][NMAX+10], s[NMAX+10];

void Lee(int p)
{   for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) sol[p][i][j] = -1;
    sol[p][poz[p].first][poz[p].second] = 0;

    Q.push(poz[p]);
    memset(viz, 0, sizeof(viz));
    viz[poz[p].first][poz[p].second] = 1;
    while(!Q.empty())
        {   pair <int, int> x = Q.front();
            Q.pop();
            for(int t=0; t<8; t++)
                {   pair <int, int> vec;
                    vec.first = x.first + dx[t];
                    vec.second = x.second + dy[t];
                    if(vec.first && vec.first <= n && vec.second && vec.second <= m
                       && !viz[vec.first][vec.second] && a[vec.first][vec.second] != 'X')
                        {   sol[p][vec.first][vec.second] = sol[p][x.first][x.second] + 1;
                            viz[vec.first][vec.second] = 1;
                            Q.push(vec);
                        }
                }
        }
}

int main()
{
    f >> n >> m;
    f.get();
    for(int i=1; i<=n; i++)
        {   f.getline(s, 105);
            for(int j=0; j<m; j++)
                {   a[i][j+1] = s[j];
                    if(s[j] == 'R') poz[1] = make_pair(i, j+1);
                    else if(s[j] == 'J') poz[2] = make_pair(i, j+1);
                }
        }
    Lee(1);
    Lee(2);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(sol[1][i][j] != -1 && sol[1][i][j] == sol[2][i][j] && sol[1][i][j] < ans)
                {   ans = max(sol[1][i][j], sol[2][i][j]);
                    coord = make_pair(i, j);
                }
    g << ans+1 << ' ' << coord.first << ' ' << coord.second << '\n';
    return 0;
}