Cod sursa(job #1338360)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 9 februarie 2015 23:04:30
Problema Rj Scor 100
Compilator cpp Status done
Runda simulareoji2015cl10 Marime 2.08 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <utility>

#define NMAX 100
using namespace std;

char mat[NMAX+5][NMAX+5];

int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1};

int dist1[NMAX+5][NMAX+5];
int dist2[NMAX+5][NMAX+5];

queue<pair<int,int> > coada;

int main()
{
    ifstream cin("rj.in");
    ofstream cout("rj.out");

    int n=1,m=1;
    cin>>n>>m;

    int i;
    for(i=1;i<=n;i++) {
        cin.get();
        cin.get(mat[i]+1,NMAX+5);
    }

    //BFS-R
    int j,k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(mat[i][j]=='R') {
                coada.push(make_pair(i,j));
                dist1[i][j]=1;
            }

    pair<int,int> y;
    int nx,ny;
    while(!coada.empty()) {
        y=coada.front();
        coada.pop();

        for(k=0;k<8;k++) {
            nx=y.first+dx[k];
            ny=y.second+dy[k];

            if(nx>=1 && ny>=1 && nx<=n && ny<=m && !dist1[nx][ny] && mat[nx][ny]!='X') {
                dist1[nx][ny]=1+dist1[y.first][y.second];
                coada.push(make_pair(nx,ny));
            }
        }
    }

    //BFS-J
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(mat[i][j]=='J') {
                coada.push(make_pair(i,j));
                dist2[i][j]=1;
            }

    while(!coada.empty()) {
        y=coada.front();
        coada.pop();

        for(k=0;k<8;k++) {
            nx=y.first+dx[k];
            ny=y.second+dy[k];

            if(nx>=1 && ny>=1 && nx<=n && ny<=m && !dist2[nx][ny] && mat[nx][ny]!='X') {
                dist2[nx][ny]=1+dist2[y.first][y.second];
                coada.push(make_pair(nx,ny));
            }
        }
    }

    int t=2000000005,l,c;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(dist1[i][j] && dist1[i][j]==dist2[i][j])
                if(dist1[i][j]<t) {
                    t=dist1[i][j];
                    l=i;
                    c=j;
                }

    cout<<t<<' '<<l<<' '<<c<<'\n';
    cin.close();
    cout.close();
    return 0;
}