Cod sursa(job #2139656)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 22 februarie 2018 18:04:49
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct FLOOD{
int x,y;
};

queue<FLOOD>q;
int dx[] = {0,1,0,-1,1,1,-1,-1};
int dy[] = {1,0,-1,0,1,-1,1,-1};
const int NMAX = 105;
int n , m , xi1,xi2,yi1,yi2;
int a[NMAX][NMAX],d[NMAX][NMAX],d1[NMAX][NMAX];
char s[NMAX];

void lee1()
{
    FLOOD temp,temp1;
    temp.x = xi1;
    temp.y = yi1;
    q.push(temp);
    d[temp.x][temp.y] = 1;
    while(!q.empty())
    {
        temp = q.front();
        q.pop();
        for(int i = 0 ; i < 8 ; i++)
        {
            temp1.x = temp.x + dx[i];
            temp1.y = temp.y + dy[i];
            if(a[temp1.x][temp1.y] == 0 && d[temp1.x][temp1.y] == 0)
            {
                q.push(temp1);
                d[temp1.x][temp1.y] = d[temp.x][temp.y] + 1;
            }
        }
    }
}

void lee2()
{
    FLOOD temp,temp1;
    temp.x = xi2;
    temp.y = yi2;
    q.push(temp);
    d1[temp.x][temp.y] = 1;
    while(!q.empty())
    {
        temp = q.front();
        q.pop();
        for(int i = 0 ; i < 8 ; i++)
        {
            temp1.x = temp.x + dx[i];
            temp1.y = temp.y + dy[i];
            if(a[temp1.x][temp1.y] == 0 && d1[temp1.x][temp1.y] == 0)
            {
                q.push(temp1);
                d1[temp1.x][temp1.y] = d1[temp.x][temp.y] + 1;
            }
        }
    }
}
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    scanf("%d%d\n",&m,&n);
    for(int i = 1 ; i <= m ; i++)
    {
        gets(s);
        for(int j = 0 ; j < strlen(s) ; j++)
        {
            if(s[j] == 'X')
                a[i][j+1] = -1;
            else if(s[j] == 'R')
            {
                xi1 = i;
                yi1 = j+1;
            }
            else if(s[j] == 'J')
            {
                xi2 = i;
                yi2 = j+1;
            }
        }
    }
    for(int i = 0 ; i <= m+1 ; i++)
        a[i][0] = a[i][n+1] = -1;
    for(int j = 0 ; j <= n+1 ; j++)
        a[0][j] = a[m+1][j] = -1;
    lee1();
    lee2();
    int posx,posy,mi = 2000000;
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 1;  j <= n ; j++)
        {
            if(a[i][j] != -1 && d[i][j] == d1[i][j] && d[i][j] != 0)
            {
                if(d[i][j] < mi)
                {
                    mi = d[i][j];
                    posx = i;
                    posy = j;
                }
            }
        }
    }
    printf("%d %d %d",mi,posx,posy);
    return 0;
}