Cod sursa(job #1927591)

Utilizator sergiudnyTritean Sergiu sergiudny Data 15 martie 2017 11:53:20
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <iostream>
#include <utility>
#include <queue>
#include <climits>
#include <string.h>
#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,102);
        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;
                if(a[ ind1+dy[i] ][ ind2+dx[i] ]==b[ ind1+dy[i] ][ ind2+dx[i] ]){
                    if(mn>a[ ind1+dy[i] ][ ind2+dx[i] ])
                        mn=a[ ind1+dy[i] ][ ind2+dx[i] ],rez1=ind1+dy[i],rez2=ind2+dx[i];
                    else if(mn==a[ ind1+dy[i] ][ ind2+dx[i] ] && rez2>ind2)
                        rez1=ind1+dy[i],rez2=ind2+dx[i];
                }
            }
        }
        q.pop();
    }
    fout<<mn<<" "<<rez1<<" "<<rez2;

    return 0;
}