Cod sursa(job #2181856)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 21 martie 2018 21:26:59
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <cstdio>
#include <queue>
using namespace std;
queue < pair<int,int> > v1;
queue < pair<int,int> > v2;
int dist1[105][105],dist2[105][105],viz1[105][105],viz2[105][105];
char mat[105][105];
const int dx[] = {-1, 0, 1,  0, -1, 1,  1, -1};
const int dy[] = { 0, 1, 0, -1, -1, -1, 1, 1};
bool verif1(int x,int y)
{
    if(mat[x][y]==' '||mat[x][y]=='J')
        return 1;
    return 0;
}
bool verif2(int x,int y)
{
    if(mat[x][y]==' '||mat[x][y]=='R')
        return 1;
    return 0;
}
void lee1()
{
    while(!v1.empty())
    {
        pair <int,int> val=v1.front();
        v1.pop();
        for(int i=0;i<=7;i++)
        {
            if(verif1(val.first+dx[i],val.second+dy[i])==1)
            {
                if(viz1[val.first+dx[i]][dy[i]+val.second]==0)
                {
                    dist1[val.first+dx[i]][dy[i]+val.second]=dist1[val.first][val.second]+1;
                    viz1[dx[i]+val.first][dy[i]+val.second]=1;
                    v1.push(make_pair(dx[i]+val.first,dy[i]+val.second));
                }
            }
        }
    }
}
void lee2()
{
    while(!v2.empty())
    {
        pair <int,int> val=v2.front();
        v2.pop();
        for(int i=0;i<=7;i++)
        {
            if(verif2(val.first+dx[i],val.second+dy[i])==1)
            {
                if(viz2[val.first+dx[i]][dy[i]+val.second]==0)
                {
                    dist2[val.first+dx[i]][dy[i]+val.second]=dist2[val.first][val.second]+1;
                    viz2[dx[i]+val.first][dy[i]+val.second]=1;
                    v2.push(make_pair(dx[i]+val.first,dy[i]+val.second));
                }
            }
        }
    }
}

int main()
{   freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int n,m,min=20000000,t,l,cnt;
    char ch;
    scanf("%d%d\n",&n,&m);
    for(int i=0;i<=n+1;i++)
    {
        mat[i][0]=mat[i][m+1]='X';
    }
    for(int i=0;i<=m+1;i++)
    {
        mat[0][i]=mat[n+1][i]='X';
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%c",&ch);
            mat[i][j]=ch;
            if(mat[i][j]=='R')
            {
                  v1.push(make_pair(i,j));
                  dist1[i][j]=1;
            }
            if(mat[i][j]=='J')
            {
                  v2.push(make_pair(i,j));
                  dist2[i][j]=1;
            }

        }
        scanf("\n");
    }
    lee1();
    lee2();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(dist1[i][j]==dist2[i][j]&&dist1[i][j]!=0)
            {
                if(dist1[i][j]<min)
                {
                    min=dist1[i][j];
                    cnt=dist1[i][j];
                    t=i;
                    l=j;
                }
            }
        }
    }
    printf("%d %d %d",cnt,t,l);
    return 0;
}