Cod sursa(job #504270)

Utilizator cristian9Cristian Zloteanu cristian9 Data 27 noiembrie 2010 12:09:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include<stdio.h>

int di[9]={0, -1, -1, 0, 1, 1,  1,  0, -1};
int dj[9]={0,  0,  1, 1, 1, 0, -1, -1, -1};

struct coada{
    int i, j, cost;
};

coada q1[10000], q2[10000], a1, a2;

int main(){
    freopen ("rj.in", "r", stdin);
    freopen ("rj.out", "w", stdout);

    int n, m, r[102][102], ju[102][102], i, j, ri, rj, ji, jj;
    char c;

    scanf("%d %d ", &n, &m);

    for(i=1; i<=n; i++)
        for(j=1; j<=m+1; j++){
            scanf("%c", &c);
            if(j!=m+1){
                if(c==' '){
                    r[i][j]=999999;
                    ju[i][j]=999999;
                }
                if(c=='R'){
                    r[i][j]=0;
                    ju[i][j]=999999;
                    ri=i;
                    rj=j;
                }
                if(c=='J'){
                    r[i][j]=999999;
                    ju[i][j]=0;
                    ji=i;
                    jj=j;
                }
                if(c=='X'){
                    r[i][j]=-1;
                    ju[i][j]=-1;
                }
            }
        }

    int iv, jv, in=0, sf1=1, sf2=1;
    q1[1].i=ri;
    q1[1].j=rj;
    q2[1].i=ji;
    q2[1].j=jj;
    while(in<=sf1 && in<=sf2){
        in++;
        a1=q1[in];
        a2=q2[in];
        for(i=1; i<=8; i++){
            iv=a1.i+di[i];
            jv=a1.j+dj[i];
            if(in<=sf2)
                if(1<=iv && iv<=n && 1<=jv && jv<=m && a1.cost+1<r[iv][jv]){
                    sf1++;
                    q1[sf1].i=iv;
                    q1[sf1].j=jv;
                    q1[sf1].cost=a1.cost+1;
                    r[iv][jv]=a1.cost+1;
                }
            iv=a2.i+di[i];
            jv=a2.j+dj[i];
            if(in<=sf2)
                if(1<=iv && iv<=n && 1<=jv && jv<=m && a2.cost+1<ju[iv][jv]){
                    sf2++;
                    q2[sf2].i=iv;
                    q2[sf2].j=jv;
                    q2[sf2].cost=a2.cost+1;
                    ju[iv][jv]=a2.cost+1;
                }
        }
    }

    int min=999999;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(r[i][j]==ju[i][j] && r[i][j]!=-1 && r[i][j]!=99999)
                if(r[i][j]<min){
                    min=r[i][j];
                    ri=i;
                    rj=j;
                }

    printf("%d %d %d ", min+1, ri, rj);

    return 0;
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++)
            printf("%d ", r[i][j]);
        printf("\n");
    }
    printf("\n");
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++)
            printf("%d ", ju[i][j]);
        printf("\n");
    }

    return 0;
}