Cod sursa(job #2482055)

Utilizator CybotStancila Ionut-Marian Cybot Data 27 octombrie 2019 19:06:59
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <queue>
#include <fstream>
#include <cstring>
#include <utility>
#include <iostream>
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int r[105][105], jul[105][105], n, m, cn, ln, lc, cc;
int tmin=1e9+1;
char s[105];
int dx[]={-1, -1, 0, 1, 1, 1, 0, -1};
int dy[]={0, 1, 1, 1, 0, -1, -1, -1};

struct p{
 int x, y;
}start1, start2, pnou;

queue < pair <int, int> > q;

void bordare()
{ for (int i=0;i<=n+1;i++) r[i][0]=jul[i][0]=r[i][n+1]=jul[i][n+1]=-1;
  for (int i=0;i<=m+1;i++) r[0][i]=jul[0][i]=r[m+1][i]=jul[m+1][i]=-1;
}

void citire()
{ f>>n>>m;
  f.get();
  for (int i=1;i<=n;i++)
  { f.getline(s, 105);
    for (int j=0;j<m;j++)
    { if (s[j]=='X') r[i][j+1]=jul[i][j+1]=-1;
      else if (s[j]==' ') r[i][j+1]=jul[i][j+1]=0;
      else if (s[j]=='R')
      { start1.x=i;
        start1.y=j+1;
      }
      else if (s[j]=='J')
      { start2.x=i;
        start2.y=j+1;
      }
    }
  }
  bordare();
}

bool okR(int l, int c)
{
    return l>0 && l<n+1 && c>0 && c<m+1 && r[l][c]==0;
}

bool okJ(int l, int c)
{
    return l>0 && l<n+1 && c>0 && c<m+1 && jul[l][c]==0;
}

void leeR()
{
    r[start1.x][start1.y]=1;
    q.push(make_pair(start1.x,start1.y));
    while (!q.empty())
    { lc=q.front().first;
      cc=q.front().second;
      q.pop();
      for (int k=0;k<8;k++)
      { ln=lc+dx[k];
        cn=cc+dy[k];
        if (okR (ln, cn)==1 )
        { r[ln][cn]=r[lc][cc]+1;
          q.push(make_pair(ln,cn));
        }
      }
    }
}

void leeJ()
{
    jul[start2.x][start2.y]=1;
    q.push(make_pair(start2.x, start2.y));
    while (!q.empty())
    { lc=q.front().first;
      cc=q.front().second;;
      q.pop();
      for (int k=0;k<8;k++)
      { ln=lc+dx[k];
        cn=cc+dy[k];
        if (okJ (ln, cn)==1 )
        { jul[ln][cn]=jul[lc][cc]+1;
          q.push(make_pair(ln,cn));
        }
      }
    }
}

void afisare()
{
  int linie, coloana;
  for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    { if (r[i][j]==jul[i][j] && tmin>r[i][j] && r[i][j]>0)
      { tmin=r[i][j];
        linie=i;
        coloana=j;
      }
    }
  g<<tmin<<" "<<linie<<" "<<coloana<<'\n';
}

int main()
{
    citire();
    leeR();
    leeJ();
    afisare();
    return 0;
}