Cod sursa(job #1837499)

Utilizator Stefania189StefaniaB Stefania189 Data 29 decembrie 2016 19:40:03
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n,m,i,j,xs,ys,xf,yf, nr[103][103], nj[103][103], nrr, p ,u, x, y, k, lv,cv, A,B;
short dx[8]={-1,-1,0,1,1,1,0,-1}, dy[8]={0,1,1,1,0,-1,-1,-1};
bool a[103][103];
char c[103];
struct elem{
  short l,c;
}R[10001], J[10001];
int main()
{
  f>>n>>m;
  f.get();
  for(i=1;i<=n;i++) {
    f.getline(c, 103);
    for(j=0;j<m;j++) {
      if(c[j]=='R') {
        xs=i;
        ys=j+1;
      }
      if(c[j]=='J') {
        xf=i;
        yf=j+1;
      }
      if(c[j]=='X') a[i][j+1]=1;
      if(c[j]==' ') a[i][j+1]=0;
      nr[i][j+1]=10000000;
      nj[i][j+1]=10000000;
    }
  }
  for(i=0;i<=n+1;i++) {
    a[i][0]=a[i][m+1]=1;
  }
  for(j=0;j<=m+1;j++) {
    a[0][j]=a[n+1][j]=1;
  }
//  for(i=0;i<=n+1;i++) {
//    for(j=0;j<=m+1;j++)
//      g<<A[i][j]<<" ";
//  g<<"\n";
//  }
    p=u=1;
    R[p].l=xs;
    R[p].c=ys;
    J[p].l=xf;
    J[p].c=yf;
    nr[xs][ys]=1;
    nj[xf][yf]=1;
    while(p<=u){
      x=R[p].l;
      y=R[p].c;
      for(k=0;k<8;k++) {
        lv=x+dx[k];
        cv=y+dy[k];
        if(lv>0 && lv<=n && cv>0 && cv<=m && a[lv][cv]==0 && nr[lv][cv]>nr[x][y]+1) {
             u++;
             R[u].l=lv; R[u].c=cv;
             nr[lv][cv]=nr[x][y]+1;
        }
      }
      p++;
    }
    p=u=1;
    while(p<=u){
      x=J[p].l;
      y=J[p].c;
      for(k=0;k<8;k++) {
        lv=x+dx[k];
        cv=y+dy[k];
        if(lv>0 && lv<=n && cv>0 && cv<=m && a[lv][cv]==0 && nj[lv][cv]>nj[x][y]+1) {
             u++;
             J[u].l=lv; J[u].c=cv;
             nj[lv][cv]=nj[x][y]+1;
        }
      }
      p++;
    }
    nrr=10000000;
    for (i=1; i<=n; i++){
        for (j=1; j<=m; j++){
            if (nr[i][j]==nj[i][j]){
                if (nr[i][j]<nrr){
                    nrr=nr[i][j];
                    A=i; B=j;
                }
            }
        }
    }
    g<<nrr<<" "<<A<<" "<<B;
  return 0;
}