Cod sursa(job #1155692)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 27 martie 2014 08:58:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <cstdio>
#include <cstring>
using namespace std;

#define JUL 150
#define ROM 250
#define MAX 105
struct coada
{
    int x,y;
}q[MAX*MAX];

int mat[MAX][MAX],matjl[MAX][MAX],viz[MAX][MAX];
coada tata, fiu;
int dx[]={-1,0,1,0,1,1,-1,-1}; //initializare pentru avansare
int dy[]={0,1,0,-1,1,-1,1,-1};
int main()
{

    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int n,m,i,j,julx,july,romx,romy,p,u,ii,jj,minim,mini,minj;
    char prop[MAX];
    scanf("%d%d\n",&n,&m);
    for(i=1; i<=n; i++){
        gets(prop);
        for(j=0; j<strlen(prop); j++)
        {
            if(prop[j]=='X')
                {mat[i][j+1]=-1;matjl[i][j+1]=-1;}
            else if(prop[j]=='J'){julx=i; july=j+1;}
            else if(prop[j]=='R'){romx=i; romy=j+1;}
            else if(prop[j]==' ')
                {mat[i][j+1]=0; matjl[i][j+1]=0;}
            //nu este nevoie de if pt cazul cu spatiu
            //ramane pt romeo mat
        }
    }
    mat[romx][romy]=1;
    q[1].x=romx; q[1].y=romy; p=1; u=1;
    while(p<=u)
    {
        for(i=0; i<=7; i++)
        {
            ii= dx[i]+q[p].x; jj=dy[i]+q[p].y;
            if(ii<1 or ii>n or jj<1 or jj>m)
                continue;
            if(mat[ii][jj] == 0 and viz[ii][jj]==0)
            {
                mat[ii][jj] = mat[q[p].x][q[p].y]+1;
                u++;
                q[u].x=ii; q[u].y=jj;
                viz[ii][jj]=1;
            }
            if(ii==julx and jj==july){ break;}
        }
        p++;
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            viz[i][j]=0;
    matjl[julx][july]=1;
    q[1].x=julx; q[1].y=july; p=1; u=1;
    while(p<=u)
    {
        for(i=0; i<=7; i++)
        {
            ii= dx[i]+q[p].x; jj=dy[i]+q[p].y;
            if(ii<1 or ii>n or jj<1 or jj>m)
                continue;
            if(matjl[ii][jj] == 0 and viz[ii][jj]==0)
            {
                matjl[ii][jj] = matjl[q[p].x][q[p].y]+1;
                u++;
                q[u].x=ii; q[u].y=jj;
                viz[ii][jj]=1;
            }
            if(ii==romx and jj==romy){
            break;}
        }
        p++;
    }
    mini=0; minj=0; mat[0][0]=100000000000;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(mat[i][j]>0 and mat[i][j] == matjl[i][j] and mat[mini][minj]>mat[i][j])
            {
                mini=i; minj=j;
            }
    printf("%d %d %d\n",mat[mini][minj],mini,minj);
    /*for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
            printf("%3d ",mat[i][j]);
        printf("\n");
    } printf("\n");
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
            printf("%3d ",matjl[i][j]);
        printf("\n");
    }*/
    return 0;
}