Cod sursa(job #1330670)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 30 ianuarie 2015 21:13:38
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <utility>

#define NMAX 100
using namespace std;

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

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

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<4;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<4;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));
            }
        }
    }

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(dist1[i][j] && dist1[i][j]==dist2[i][j]) {
                cout<<dist1[i][j]-1<<' '<<i<<' '<<j<<'\n';

                cin.close();
                cout.close();
                return 0;
            }

    //cin.close();
    //cout.close();
    return 0;
}