Cod sursa(job #1330654)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 30 ianuarie 2015 20:54:27
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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 dist[NMAX+5][NMAX+5];
pair<int,int> prec[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);
    }

    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));
                dist[i][j]=1;
            }

    pair<int,int> y;
    int nx,ny;

    int lf,cf;
    while(!coada.empty()) {
        y=coada.front();
        coada.pop();

        if(mat[y.first][y.second]=='J') {
            lf=y.first;
            cf=y.second;

            break;
        }

        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 && !dist[nx][ny] && mat[nx][ny]!='X') {
                dist[nx][ny]=1+dist[y.first][y.second];
                prec[nx][ny]=y;
                coada.push(make_pair(nx,ny));
            }
        }
    }

    int time=dist[lf][cf]/2;

    pair<int,int> curent=make_pair(lf,cf);
    for(int i=0;i<time;i++)
        curent=prec[curent.first][curent.second];

    cout<<time<<' '<<curent.first<<' '<<curent.second<<'\n';

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