Cod sursa(job #1122489)
Utilizator | 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;
}