Cod sursa(job #2308390)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 26 decembrie 2018 23:52:22
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
queue < pair<int,int> > coada,coada2;
int lin[]={-1,-1,0,1,1,1,0,-1};
int col[]={0,1,1,1,0,-1,-1,-1};
int n,m,i,j,startx,starty,finx,finy,a[102][102],b[102][102],ni,nj;
char car[105];
int main()
{
   fin>>n>>m;
   fin.getline(car,106);
   for(i=1;i<=n;i++){
    fin.getline(car,106);
    for(j=0;j<m;j++)
    if(car[j]=='X')
        a[i][j+1]=b[i][j+1]=-1;
    else if(car[j]=='R'){
        startx=i;
        starty=j+1;
        a[i][j+1]=1;
    }
     else if(car[j]=='J'){
        finx=i;
        finy=j+1;
        b[finx][finy]=1;
    }
   }



   coada.push(make_pair(startx,starty));
   coada2.push(make_pair(finx,finy));
   while(coada.empty()==0){
    i=coada.front().first;
    j=coada.front().second;
    coada.pop();
    for(int d=0;d<8;d++){
        ni=i+lin[d];
        nj=j+col[d];
        if(ni<=n&&nj<=m&&ni>=1&&nj>=1&&a[ni][nj]==0){
            a[ni][nj]=a[i][j]+1;
            coada.push(make_pair(ni,nj));
        }
    }

   }
    while(coada2.empty()==0){
    i=coada2.front().first;
    j=coada2.front().second;
    coada2.pop();
    for(int d=0;d<8;d++){
        ni=i+lin[d];
        nj=j+col[d];
        if(ni<=n&&nj<=m&&ni>=1&&nj>=1&&b[ni][nj]==0){
            b[ni][nj]=b[i][j]+1;
            coada2.push(make_pair(ni,nj));
        }
    }

   }
   int sol=100000000,solx,soly;
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
  if(a[i][j]>0&&a[i][j]==b[i][j]&&sol>a[i][j]){
    solx=i;
    soly=j;
    sol=a[i][j];
  }
  fout<<a[solx][soly]<<" "<<solx<<" "<<soly;
}