Cod sursa(job #1874484)

Utilizator aeromaniaXRadoi Iulian aeromaniaX Data 10 februarie 2017 00:47:55
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;
int n,m,xs2,ys2,xs1,ys1,nr[103][103],nr2[103][103],xf,yf,Min;
bool a[103][103];
short dx[]={-1,-1,0,1,1,1,0,-1};
short dy[]={0,1,1,1,0,-1,-1,-1};
char c;

void af(int a[103][103])
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d ",a[i][j]);
    printf("\n");
}
}

struct meh{
    int c;
    int l;
}x,y;
queue <meh> q;

void bordare()
{
    for(int i=0;i<=n+1;i++)
            a[i][0]=a[i][m+1]=1;
    for(int j=0;j<=m+1;j++)
            a[0][j]=a[n+1][j]=1;

}


void lee(int nr[103][103])
{
int k,lv,cv;
    while(!q.empty())
    {
        x=q.front();
        q.pop();


        for(k=0;k<8;k++)
        {
            lv=dx[k]+x.l;
            cv=dy[k]+x.c;

            if(a[lv][cv]==0 && nr[lv][cv]>nr[x.l][x.c]+1)
            {
                y.l=lv;
                y.c=cv;
                q.push(y);
                nr[lv][cv]=nr[x.l][x.c]+1;
            }
        }
    }
}



void cit()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
}



int main()
{
    cit();
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
scanf("\n");
        for(int j=1;j<=m;j++){
            scanf("%c",&c);

            if(c=='R'){
                xs1=i;
                ys1=j;
            }
            else if(c=='J')
            {
                xs2=i;
                ys2=j;
            }
            else if(c=='X')
                a[i][j]=1;
            nr[i][j]=999999;
            nr2[i][j]=999999;
    }
    }
    nr[xs1][ys1]=1;
    nr2[xs2][ys2]=1;

    x.l=xs1;x.c=ys1;
    q.push(x);

    lee(nr);
    x.l=xs2;x.c=ys2;
    q.push(x);

    lee(nr2);

    Min=99999999;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(nr[i][j]==nr2[i][j] && nr[i][j]<Min)
    {
            Min=nr[i][j];
            xf=i;
            yf=j;
    }
    printf("%d %d %d",Min,xf,yf);


    return 0;
}