Cod sursa(job #1642841)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 9 martie 2016 16:28:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <stdio.h>

using namespace std;
FILE *fin=fopen("rj.in" ,"r");
FILE *fout=fopen("rj.out" , "w");
int dir1[9]={ 0 , 0 , -1 , -1, -1, 1 ,1 ,1};
int dir2[9]={ -1 , 1 , 0 , -1 ,1 , 0 , -1 , 1};
struct perechi
{
    int lin , col;
};
perechi q[10010] , y , start;
int d1[102][102] , d2[102][102];
int a[102][102];
char c[103];
int main()
{
    int n , m , poz1 , poz2 , poz11 , poz22 , i , j , minn=1000000 , linbun , colbun;
    fscanf(fin , "%d%d" , &n , &m);
    fgets(c, 100 , fin);
    for(i=0;i<=n+1;i++)
        for(j=0;j<=m+1;j++)
    {
        d1[i][j]=0;
        a[i][j]=0;
    }
    for(i=1;i<=n;i++)
    {
        a[i][m+1]=1;
        a[i][0]=1;
        fgets(c , 102 , fin);
        for(j=0;j<m;j++)
        {
            if(c[j]==' ') a[i][j+1]=0;
            if(c[j]=='X') a[i][j+1]=1;
            if(c[j]=='R')
            {
                a[i][j+1]=2;
                poz1=i;
                poz2=j+1;
            }
            if(c[j]=='J')
            {
                a[i][j+1]=2;
                poz11=i;
                poz22=j+1;
            }
        }
    }
    int p=0 , u=-1;
    start.lin=poz1;
    start.col=poz2;
    q[++u]=start;
    d1[start.lin][start.col]=1;
    while(p<=u)
    {
        start=q[p++];
        for(i=0 ; i<8 ; i++)
        {
            y.lin=start.lin + dir1[i];
            y.col=start.col + dir2[i];
            if(a[y.lin][y.col]==0 && d1[y.lin][y.col]==0 && y.lin>0 && y.lin<=n && y.col>0 && y.col<=n)
            {
                q[++u]=y;
                d1[y.lin][y.col]= 1+d1[start.lin][start.col];
            }
        }
    }
    p=0 , u=-1;
    start.lin=poz11;
    start.col=poz22;
    q[++u]=start;
    d2[start.lin][start.col]=1;
    while(p<=u)
    {
        start=q[p++];
        for(i=0 ; i<8 ; i++)
        {
            y.lin=start.lin + dir1[i];
            y.col=start.col + dir2[i];
            if(a[y.lin][y.col]==0 && d2[y.lin][y.col]==0 && y.lin>0 && y.lin<=n && y.col>0 && y.col<=n)
            {
                q[++u]=y;
                d2[y.lin][y.col]= 1+d2[start.lin][start.col];
            }
        }
    }
    for(i=n;i>=1;i--)
        for(j=m;j>=1;j--)
    {
        if(d1[i][j]==d2[i][j] && d1[i][j] < minn && d1[i][j]>0)
        {
            linbun=i;
            colbun=j;
            minn=d1[i][j];
        }
    }
    fprintf(fout , "%d %d %d" , linbun , colbun , minn);
    return 0;
}