Pagini recente » Istoria paginii utilizator/edyiordache | Istoria paginii utilizator/tliviu | Istoria paginii utilizator/dana24hd | Istoria paginii utilizator/iacobtudor | Cod sursa (job #369344)
Cod sursa(job #369344)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int i,j,k,m,n,minim=50000,minim2=50000,minim3=50000,a[105][105],o[105][105],o2[105][105],l,tmin,pozi,pozj,poz1,poz2,qi1[50000],jnou,inou,poz3,poz4;
char x,s[105],qi[50000],qj[50000],qj1[50000],q2[50000];
int first,last;
int isempty()
{if (first == last)
return 1;
else return 0;}
int main(){
f>>n>>m;
f.getline(s,100);
for(i=1;i<=n;i++)
{f.getline(s,105);
//cout<<s<<strlen(s)<<endl;
for(k=0;k<m;k++)
{if(s[k]=='R')
a[i][k+1]=10;
if(s[k]=='J')
a[i][k+1]=20;
if(s[k]==' ')
a[i][k+1]=1;
if(s[k]=='X')
a[i][k+1]=0;}
}
/* for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<a[i][j]<<" ";
cout<<endl;}
} */
for(i=0;i<=n+1;i++)
{a[i][0]=-2;
a[i][m+1]=-2;}
for(i=0;i<=m+1;i++)
{a[0][i]=-2;
a[n+1][i]=-2;}
/*for(i=0;i<=n+1;i++)
{for(j=0;j<=m+1;j++)
cout<<a[i][j]<<" ";
cout<<endl;}}*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{if(a[i][j]==10)
{poz1=i;
poz2=j;}
if(a[i][j]==20)
{poz3=i;
poz4=j;}}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
o[i][j]=n*n*n;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
o2[i][j]=n*n*n;
qi[last]=poz1;
qj[last]=poz2;
qi1[last]=poz3;
qj1[last]=poz4;
o[poz1][poz2]=1;
o2[poz3][poz4]=1;
last=1;
while(!isempty())
{
i=qi[first];
j=qj[first];
first++;
inou = i+1;
jnou = j;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
inou = i-1;
jnou = j;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
inou = i;
jnou = j+1;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
inou = i;
jnou = j-1;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
inou = i+1;
jnou = j-1;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
inou = i+1;
jnou = j+1;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
inou = i-1;
jnou = j+1;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
inou = i-1;
jnou = j-1;
if (a[inou][jnou] == 1)
if (o[inou][jnou] > 1+ o[i][j])
{
o[inou][jnou] = 1+ o[i][j];
qi[last] = inou;
qj[last] = jnou;
last++;
}
}
first=0;
last=1;
inou=0;
jnou=0;
while(!isempty())
{
i=qi1[first];
j=qj1[first];
first++;
inou = i+1;
jnou = j;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}
inou = i-1;
jnou = j;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}
inou = i;
jnou = j+1;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}
inou = i;
jnou = j-1;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}
inou = i+1;
jnou = j-1;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}
inou = i+1;
jnou = j+1;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}
inou = i-1;
jnou = j+1;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}
inou = i-1;
jnou = j-1;
if (a[inou][jnou] == 1)
if (o2[inou][jnou] > 1+ o2[i][j])
{
o2[inou][jnou] = 1+ o2[i][j];
qi1[last] = inou;
qj1[last] = jnou;
last++;
}}
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<o2[i][j]<<" ";
cout<<endl;}
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
if(o[i][j]==n*n*n)
o[i][j]=-1;}
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
if(o2[i][j]==n*n*n)
o2[i][j]=-1;}
/*for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<o[i][j]<<" ";
cout<<endl;}
cout<<endl;*/
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
cout<<o2[i][j]<<" ";
cout<<endl;}
cout<<endl;
/*for(i=0;i<=n+1;i++)
{for(j=0;j<=m+1;j++)
cout<<a[i][j]<<" ";
cout<<endl;}*/
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)
if(o[i][j]<minim && o[i][j] == o2[i][j] && o[i][j]!=-1)
{
minim= o[i][j];
tmin = o[i][j];
pozi = i;
pozj = j;
}
}
g<<tmin<<" "<<pozi<<" "<<pozj<<" ";
return 0;}