Cod sursa(job #1122489)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 25 februarie 2014 18:26:00
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.67 kb
#include <fstream>
#include <cstdio>
using namespace std;
int v1[110][110],v2[110][110],lr,cr,lj,cj,a,col[10001],coc[10001],p,u,u1,k,o,i1,t,minim;
char c;
int main()
{
ifstream f("rj.in");ofstream g("rj.out");
int n,m,i,j;
f>>n>>m;
f.get(c);
for (i=1;i<=n;i++) {for (j=1;j<=m;j++) {f.get(c);
                                       a=c;
                                       if (a==88) {v1[i][j]=-1;v2[i][j]=-1;}
                                  else if (a==32) {v1[i][j]=10000;v2[i][j]=10000;}
                                  else if (a==82) {v1[i][j]=1;v2[i][j]=10000;lr=i;cr=j;}
                                  else if (a==74) {v1[i][j]=10000;v2[i][j]=1;lj=i;cj=j;}
                                        }
                    f.get(c);
                    }

/*for (i=1;i<=n;i++) {for (j=1;j<=m;j++) g<<v1[i][j]<<" ";g<<'\n';}
for (i=1;i<=n;i++) {for (j=1;j<=m;j++) g<<v2[i][j]<<" ";g<<'\n';}*/
p=1;u=1;
col[1]=lr;coc[1]=cr;
while (p<=u) {u1=u;
              for (i=p;i<=u;i++) {k=col[i];
                                  o=coc[i];
                                  if (v1[k+1][o]>v1[k][o]+1) {u1++;
                                                              col[u1]=k+1;coc[u1]=o;
                                                              v1[k+1][o]=v1[k][o]+1;
                                                              }
                                   if (v1[k-1][o]>v1[k][o]+1) {u1++;
                                                              col[u1]=k-1;coc[u1]=o;
                                                              v1[k-1][o]=v1[k][o]+1;
                                                              }
                                   if (v1[k][o+1]>v1[k][o]+1) {u1++;
                                                              col[u1]=k;coc[u1]=o+1;
                                                              v1[k][o+1]=v1[k][o]+1;
                                                              }
                                   if (v1[k][o-1]>v1[k][o]+1) {u1++;
                                                              col[u1]=k;coc[u1]=o-1;
                                                              v1[k][o-1]=v1[k][o]+1;
                                                              }
                                   if (v1[k+1][o+1]>v1[k][o]+1) {u1++;
                                                                 col[u1]=k+1;coc[u1]=o+1;
                                                                 v1[k+1][o+1]=v1[k][o]+1;
                                                                 }
                                   if (v1[k-1][o-1]>v1[k][o]+1) {u1++;
                                                                  col[u1]=k-1;coc[u1]=o-1;
                                                                  v1[k-1][o-1]=v1[k][o]+1;
                                                                  }
                                   if (v1[k+1][o-1]>v1[k][o]+1) {u1++;
                                                                  col[u1]=k+1;coc[u1]=o-1;
                                                                  v1[k+1][o-1]=v1[k][o]+1;
                                                                  }
                                   if (v1[k-1][o+1]>v1[k][o]+1) {u1++;
                                                                  col[u1]=k-1;coc[u1]=o+1;
                                                                  v1[k-1][o+1]=v1[k][o]+1;
                                                                  }
                                  }
              p=u+1;
              u=u1;
              }
for (i=0;i<=10000;i++) {col[i]=0;coc[i]=0;}
p=1;u=1;
col[1]=lj;coc[1]=cj;
while (p<=u) {u1=u;
              for (i=p;i<=u;i++) {k=col[i];
                                  o=coc[i];
                                  if (v2[k+1][o]>v2[k][o]+1) {u1++;
                                                              col[u1]=k+1;coc[u1]=o;
                                                              v2[k+1][o]=v2[k][o]+1;
                                                              }
                                   if (v2[k-1][o]>v2[k][o]+1) {u1++;
                                                              col[u1]=k-1;coc[u1]=o;
                                                              v2[k-1][o]=v2[k][o]+1;
                                                              }
                                   if (v2[k][o+1]>v2[k][o]+1) {u1++;
                                                              col[u1]=k;coc[u1]=o+1;
                                                              v2[k][o+1]=v2[k][o]+1;
                                                              }
                                   if (v2[k][o-1]>v2[k][o]+1) {u1++;
                                                              col[u1]=k;coc[u1]=o-1;
                                                              v2[k][o-1]=v2[k][o]+1;
                                                              }
                                   if (v2[k+1][o+1]>v2[k][o]+1) {u1++;
                                                                 col[u1]=k+1;coc[u1]=o+1;
                                                                 v2[k+1][o+1]=v2[k][o]+1;
                                                                 }
                                   if (v2[k-1][o-1]>v2[k][o]+1) {u1++;
                                                                  col[u1]=k-1;coc[u1]=o-1;
                                                                  v2[k-1][o-1]=v2[k][o]+1;
                                                                  }
                                   if (v2[k+1][o-1]>v2[k][o]+1) {u1++;
                                                                  col[u1]=k+1;coc[u1]=o-1;
                                                                  v2[k+1][o-1]=v2[k][o]+1;
                                                                  }
                                   if (v2[k-1][o+1]>v2[k][o]+1) {u1++;
                                                                  col[u1]=k-1;coc[u1]=o+1;
                                                                  v2[k-1][o+1]=v2[k][o]+1;
                                                                  }
                                  }
              p=u+1;
              u=u1;
              }
//for (i=1;i<=n;i++) {for (j=1;j<=m;j++) g<<v1[i][j]<<" ";g<<'\n';}g<<'\n';
//for (i=1;i<=n;i++) {for (j=1;j<=m;j++) g<<v2[i][j]<<" ";g<<'\n';}
minim=10000;
for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (v1[i][j]==v2[i][j]&&v1[i][j]<minim&&v1[i][j]!=-1) {minim=v1[i][j];i1=i;t=j;}
g<<minim<<" "<<i1<<" "<<t;
return 0;


}