Cod sursa(job #2482045)

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

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

int r[105][105], jul[105][105], n, m, cn, ln;
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 < p > 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({start1.x,start1.y});
    while (!q.empty())
    { pnou=q.front();
      q.pop();
      for (int k=0;k<8;k++)
      { ln=pnou.x+dx[k];
        cn=pnou.y+dy[k];
        if (okR (ln, cn)==1 )
        { r[ln][cn]=r[pnou.x][pnou.y]+1;
          q.push({ln,cn});
        }
      }
    }
}

void leeJ()
{
    jul[start2.x][start2.y]=1;
    q.push({start2.x,start2.y});
    while (!q.empty())
    { pnou=q.front();
      q.pop();
      for (int k=0;k<8;k++)
      { ln=pnou.x+dx[k];
        cn=pnou.y+dy[k];
        if (okJ (ln, cn)==1 )
        { jul[ln][cn]=jul[pnou.x][pnou.y]+1;
          q.push({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;
}