Cod sursa(job #1503323)

Utilizator andru47Stefanescu Andru andru47 Data 15 octombrie 2015 21:47:20
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>
#include <climits>
#define mp make_pair
#define f first
#define s second
using namespace std;
int a[150][150],J[150][150],r[150][150],j,i,x1,x2,yy1,y2,miny=INT_MAX,n,m,poz1,poz2;
char c;
queue < pair<int,int> > Q;
pair <int,int> X;
void lee(int a[150][150],int x,int y)
{
    int xx,yy,poz[8]={0,0,1,1,1,-1,-1,-1},pozz[8]={1,-1,-1,0,1,-1,1,0},i;
    Q.push(mp(x,y));
    while (!Q.empty())
    {
        X=Q.front();
        for (i=0;i<=7;i++)
        {
            xx=X.f+poz[i];
            yy=X.s+pozz[i];
            if(a[xx][yy]==0)
            {
                a[xx][yy]=a[X.f][X.s]+1;
                Q.push(mp(xx,yy));
            }
        }
        Q.pop();
    }

}
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            scanf("%c",&c);
            if (c=='X')
            {
                a[i][j]=-1;
            }
            else if (c==' ')
            {
                a[i][j]=0;
            }
            else if (c=='R')
            {
                x1=i;
                x2=j;
                a[i][j]=0;
            }
            else if (c=='J')
            {
                yy1=i;
                y2=j;
                a[i][j]=0;
            }
        }
        scanf("%c",&c);
    }
    for (i=0;i<=n+1;i++)
    {
        for (j=0;j<=m+1;j++)
            if (i==0||j==0||i==n+1||j==m+1)a[i][j]=-1;
    }
    memcpy(r,a,sizeof(a));
    memcpy(J,a,sizeof(a));
    lee(r,x1,x2);
    lee(J,yy1,y2);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if (r[i][j]==J[i][j]&&r[i][j]!=-1)
            {
                if (r[i][j]<miny&&r[i][j]!=0)
                {
                    poz1=i;
                    poz2=j;
                    miny=r[i][j];
                }
            }
        }
    }
    printf("%d %d %d\n",miny+1,poz1,poz2);
    return 0;
}