Cod sursa(job #1837216)

Utilizator Stefania189StefaniaB Stefania189 Data 29 decembrie 2016 11:51:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n,m,i,j,xs,ys,xf,yf,lv,cv,p,x,y,nr,u,k,a,b;
char nrr[103][103], nrj[103][103];
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, 101);
    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;
    }
  }
  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;
    nrr[xs][ys]=1;
    nrj[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 && nrr[lv][cv]>nrr[x][y]+1) {
             u++;
             R[u].l=lv; R[u].c=cv;
             nrr[lv][cv]=nrr[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 && nrj[lv][cv]>nrj[x][y]+1) {
             u++;
             J[u].l=lv; J[u].c=cv;
             nrj[lv][cv]=nrj[x][y]+1;
        }
      }
      p++;
    }
    nr=10000000;
    for (i=1; i<=n; i++){
        for (j=1; j<=m; j++){
            if (nrr[i][j]==nrj[i][j]){
                if (nrr[i][j]<nr){
                    nr=nrr[i][j];
                    a=i; b=j;
                }
            }
        }
    }
    g<<nr<<" "<<a<<" "<<b;
  return 0;
}