Cod sursa(job #2217982)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 2 iulie 2018 19:47:39
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <queue>
#define VMAX 1000000000
#define MAX 110
#define x first
#define y second

using namespace std;
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};

int n,m,l1,c1,l2,c2,tmin,lf,cf;
char c;
int d1[MAX][MAX],d2[MAX][MAX];
bool a[MAX][MAX],acc[MAX][MAX];
queue< pair<int,int> > q;
pair<int,int> ac;
bool inside(int lin,int col){
  return (lin>=1&&lin<=n&&col>=1&&col<=m);
}
void calcdis(int li,int ci,int vd[MAX][MAX]){
  for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    acc[i][j]=0;
  q.push(make_pair(li,ci));
  acc[li][ci]=1; vd[li][ci]=1;
  int la,ca;
  while(not q.empty()){
    ac=q.front(),q.pop();
    for(int d=0;d<8;d++){
      la=ac.x+dl[d],ca=ac.y+dc[d];
      if(inside(la,ca)&&!acc[la][ca]&&!a[la][ca])
        vd[la][ca]=vd[ac.x][ac.y]+1,
        acc[la][ca]=1,
        q.push(make_pair(la,ca));
    }
  }
}

int main()
{
    ifstream f ("rj.in");
    ofstream g ("rj.out");
    f>>n>>m; f.get();
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        f.get(c);
        if(c=='X')a[i][j]=1;
        else if(c=='R')l1=i,c1=j;
        else if(c=='J')l2=i,c2=j;
      }
      f.get();
    }
    calcdis(l1,c1,d1); calcdis(l2,c2,d2); tmin=VMAX;
//    for(int i=1;i<=n;i++){
//      for(int j=1;j<=m;j++)
//        cout<<d1[i][j]<<" ";
//      cout<<'\n';
//    } cout<<'\n';
//    for(int i=1;i<=n;i++){
//      for(int j=1;j<=m;j++)
//        cout<<d2[i][j]<<" ";
//      cout<<'\n';
//    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        if(d1[i][j]!=0&&d1[i][j]==d2[i][j]&&d1[i][j]<tmin){
          tmin=d1[i][j];
          lf=i;
          cf=j;
        }
    g<<tmin<<" "<<lf<<" "<<cf<<'\n';
    f.close ();
    g.close ();
    return 0;
}