Cod sursa(job #1135403)

Utilizator BaTDucKMocanu George BaTDucK Data 7 martie 2014 20:35:29
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include<stdio.h>
#include<queue>
#include<utility>
using namespace std;
const int vert[4]={-1,0,1,0};
const int oriz[4]={0,-1,0,1};
int matr[105][105],matj[105][105];
int main()
{
    int n,m,i,j;char sir[105];
    queue < pair < int, int> > coada;
    pair < int, int > coord,ro,ju;
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    scanf("%d %d\n",&m,&n);
    for(i=1;i<=m;++i){
        gets(sir);
        for(j=0;j<n;++j) {
            if(sir[j]=='X') matr[i][j+1]=matj[i][j+1]=-1;
            else if(sir[j]=='R') ro=make_pair(i,j+1);
            else if(sir[j]=='J') ju=make_pair(i,j+1);
        }
    }
    for(i=0;i<=m+1;i++)
        matr[i][0]=matr[i][m+1]=matj[i][0]=matj[i][m+1]=-1;
    for(i=0;i<=n+1;i++)
        matr[0][i]=matr[n+1][i]=matj[0][i]=matj[n+1][i]=-1;
    coada.push(ro);
    matr[ro.first][ro.second]=1;
    while(!coada.empty()){
        for(i=0;i<4;++i){
            coord=make_pair(coada.front().first+vert[i],coada.front().second+oriz[i]);
            if(!matr[coord.first][coord.second]){
    matr[coord.first][coord.second]=matr[coada.front().first][coada.front().second]+1;
    coada.push(coord);
            }
        }
        coada.pop();
    }
    coada.push(ju);
    matj[ju.first][ju.second]=1;
    while(!coada.empty()){
        for(i=0;i<4;++i){
            coord=make_pair(coada.front().first+vert[i],coada.front().second+oriz[i]);
            if(!matj[coord.first][coord.second]){
    matj[coord.first][coord.second]=matj[coada.front().first][coada.front().second]+1;
    coada.push(coord);
            }
        }
        coada.pop();
    }
    int indi,indj,minim=2000000;
    for(i=1;i<=m;++i)
        for(j=1;j<=n;++j)
            if(matr[i][j]==matj[i][j] && matr[i][j]<minim && matr[i][j]>0){
                minim=matr[i][j];
                indi=i;indj=j;
            }

    printf("%d %d %d",minim-1,indi,indj);
    fclose(stdin);fclose(stdout);
    return 0;
}