Cod sursa(job #1927905)

Utilizator sergiudnyTritean Sergiu sergiudny Data 15 martie 2017 18:00:38
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <iostream>
#include <utility>
#include <queue>
#include <climits>
#include <cstring>
#define DM 102
#define mp make_pair
#define x first
#define y second
#define pii pair<int,int>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

queue<pii>q;
int a[DM][DM],b[DM][DM];
int dx[]={0,1,1,1,0,-1,-1,-1},dy[]={1,1,0,-1,-1,-1,0,1};
int n,m,r1,r2,j1,j2,rez1,rez2,mn=INT_MAX;
char aux[DM];

bool verifa(int ind1,int ind2){
    if(!a[ind1][ind2] && ind1<=n && ind2<=m && ind1 && ind2)
        return 1;
    return 0;
}
bool verifb(int ind1,int ind2){
    if(!b[ind1][ind2] && ind1<=n && ind2<=m && ind1 && ind2)
        return 1;
    return 0;
}

int main()
{
    fin>>n>>m;
    fin.get();
    for(int i=1;i<=n;++i){
        fin.getline(aux,101);
        for(int j=0;j<m;++j){
            if(aux[j]=='R')
                r1=i,r2=j+1;
            else if(aux[j]=='J')
                j1=i,j2=j+1;
            else if(aux[j]=='X')
                a[i][j+1]=-1,b[i][j+1]=-1;
        }
    }
    q.push(mp(r1,r2));
    a[r1][r2]=1;
    while(!q.empty()){
        for(int i=0;i<8;++i){
            int ind1=q.front().x,ind2=q.front().y;
            if(verifa(ind1+dy[i],ind2+dx[i]))
                q.push(mp(ind1+dy[i],ind2+dx[i])),a[ind1+dy[i]][ind2+dx[i]]=a[ind1][ind2]+1;
        }
        q.pop();
    }
    q.push(mp(j1,j2));
    b[j1][j2]=1;
    while(!q.empty()){
        for(int i=0;i<8;++i){
            int ind1=q.front().x,ind2=q.front().y;
            if(verifb(ind1+dy[i],ind2+dx[i])){
                q.push(mp(ind1+dy[i],ind2+dx[i]));
                b[ ind1+dy[i] ][ ind2+dx[i] ]=b[ind1][ind2]+1;
            }
        }
        q.pop();
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
        if(a[i][j]==b[i][j] && a[i][j]!=-1 && a[i][j] && a[i][j]<mn)
            mn=a[i][j],rez1=i,rez2=j;

    fout<<mn<<" "<<rez1<<" "<<rez2;

    return 0;
}