Cod sursa(job #1004735)

Utilizator MaddoxMihalcea-Simoiu Theodor Maddox Data 3 octombrie 2013 16:48:02
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <cstring>
#define MAXM 110
#define MIN 10000
using namespace std;
int x,y,cost;
int Min=MIN,xx,yy,i,j,n,m,x1,x2,y1,y2,a[MAXM][MAXM],b[MAXM][MAXM];
char c,s[MAXM];
int dx[8]= {0,0,-1,1,1,-1,-1,1};
int dy[8]= {1,-1,0,0,-1,1,-1,1};
struct coada
{
    int x,y,cost;
};
coada R[MAXM*MAXM],J[MAXM*MAXM];
void bordare(int A[MAXM][MAXM])
{
    int i,j;
    for(i=0; i<=n; ++i)
        A[i][0]=a[i][m+1]=-1;
    for(j=1; j<=m; ++j)
        A[0][j]=A[n+1][j]=-1;
}
void lee(int A[MAXM][MAXM],coada C[],int xi,int yi)
{
    bordare(A);
    int i,nr=1,t=0,nx,ny;
    C[1].x=xi;
    C[1].y=yi;
    C[1].cost=1;
    A[xi][yi]=1;
    cost=0;
    for(i=1; i<=nr; ++i)
    {
        x=C[i].x;
        y=C[i].y;
        for(t=0; t<8; ++t)
        {
            nx=x+dx[t];
            ny=y+dy[t];
            if(A[nx][ny]==0)
            {
                C[++nr].x=nx;
                C[nr].y=ny;
                C[nr].cost=C[i].cost+1;
                A[nx][ny]=C[nr].cost;
            }
        }
    }
}
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(i=1; i<=n; ++i)
    {
        gets(s);
        for(j=0; j<m; ++j)
        {
            if(s[j]==' ') a[i][j+1]=0;
            if(s[j]=='R')
            {
                x1=i;
                y1=j+1;
            }
            if(s[j]=='J')
            {
                x2=i;
                y2=j+1;
            }
            if(s[j]=='X') a[i][j+1]=-1;
        }
    }
   for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
     b[i][j]=a[i][j];
   bordare(a);
   bordare(b);
   lee(a,R,x1,y1);
   lee(b,J,x2,y2);
   for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
     if(a[i][j]==b[i][j] && a[i][j]>0 && a[i][j]<Min){
      Min=a[i][j];
      xx=i;
      yy=j;
     }
     printf("%d %d %d\n",Min,xx,yy);
    return 0;
}