Cod sursa(job #2496905)

Utilizator georgecristian2002Raducanu George-Cristian georgecristian2002 Data 21 noiembrie 2019 20:22:18
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <cstdio>
#include <queue>
using namespace std;
const int INF = 2.e9;
int di[]= {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1};
int dj[]= {0 , 1 , 1 , 1 , 0 , -1 , -1 , -1};
struct poz
{
    int x , y;
};
queue <poz> q;
poz temp1 , temp2;
int romeo[105][105] , julieta[105][105] , n , m;
bool a[105][105];
char s[105];
void lee(int x , int y , int l[105][105])
{
    int i , j;
    temp1.x = x;
    temp1.y = y;
    q.push(temp1);
    while(!q.empty())
    {
        temp1 = q.front();
        q.pop();
        for(i = 0 ; i < 8 ; i ++)
        {
            temp2.x = temp1.x + di[i];
            temp2.y = temp1.y + dj[i];
            if(temp2.x >= 1 && temp2.x <= n && temp2.y >= 1 && temp2.y <= m && a[temp2.x][temp2.y] == 0 && l[temp1.x][temp1.y] + 1 < l[temp2.x][temp2.y])
            {
                l[temp2.x][temp2.y] = l[temp1.x][temp1.y] + 1;
                q.push(temp2);
            }
        }
    }
}
int main()
{
    freopen("rj.in" , "r" , stdin);
    freopen("rj.out" , "w" , stdout);
    int i , j , xr , yr , xj , yj , x , y , minim;
    scanf("%d%d\n" , &n , &m);
    for(i = 1 ; i <= n ; i ++)
    {
        gets(s + 1);
        for(j = 1 ; j <= m ; j ++)
        {
            if(s[j] == 'R')
            {
                xr = i;
                yr = j;
            }
            else if(s[j] == 'J')
            {
                xj = i;
                yj = j;
            }
            else if(s[j] == 'X')
                a[i][j] = 1;
            romeo[i][j] = julieta[i][j] = INF;
        }
    }
    julieta[xj][yj] = 1;
    lee(xj , yj , julieta);
    romeo[xr][yr] = 1;
    lee(xr , yr , romeo);
    minim = INF;
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= m ; j ++)
            if(julieta[i][j] == romeo[i][j] && julieta[i][j] < minim)
            {
                minim = julieta[i][j];
                x = i;
                y = j;
            }
    printf("%d %d %d\n" , minim , x , y);
    return 0;
}