Pagini recente » Cod sursa (job #2279558) | Cod sursa (job #1844708) | Cod sursa (job #1520198) | Cod sursa (job #1686834) | Cod sursa (job #981351)
Cod sursa(job #981351)
#include<stdio.h>
#include<stack>
using namespace std;
typedef struct punct
{
char x,y;
}punct;
char v[110][110];
int a[110][110],b[110][110];
int n,m,nr,x,y,k,sol=2000000000,solx,soly,i=1,j;
punct aux;
//stack <punct> st;
punct st[10004];
void lee1()
{
st[++j]=aux;
a[aux.x][aux.y]=1;
while(i<=j)
{
x=st[i].x;
y=st[i].y;
k=a[x][y];
++i;
if(k>=sol-1)
continue;
if(x>0&&v[x-1][y]==' '&&(a[x-1][y]==0||a[x-1][y]>k+1))
{
a[x-1][y]=k+1;
aux.x=x-1;
aux.y=y;
st[++j]=aux;
}
if(y>0&&v[x][y-1]==' '&&(a[x][y-1]==0||a[x][y-1]>k+1))
{
a[x][y-1]=k+1;
aux.x=x;
aux.y=y-1;
st[++j]=aux;
}
if(x<n-1&&v[x+1][y]==' '&&(a[x+1][y]==0||a[x+1][y]>k+1))
{
a[x+1][y]=k+1;
aux.x=x+1;
aux.y=y;
st[++j]=aux;
}
if(y<m-1&&v[x][y+1]==' '&&(a[x][y+1]==0||a[x][y+1]>k+1))
{
a[x][y+1]=k+1;
aux.x=x;
aux.y=y+1;
st[++j]=aux;
}
///////////////////////////
if(x>0&&y>0&&v[x-1][y-1]==' '&&(a[x-1][y-1]==0||a[x-1][y-1]>k+1))
{
a[x-1][y-1]=k+1;
aux.x=x-1;
aux.y=y-1;
st[++j]=aux;
}
if(x<n-1&&y>0&&v[x+1][y-1]==' '&&(a[x+1][y-1]==0||a[x+1][y-1]>k+1))
{
a[x+1][y-1]=k+1;
aux.x=x+1;
aux.y=y-1;
st[++j]=aux;
}
if(x<n-1&&y<m-1&&v[x+1][y+1]==' '&&(a[x+1][y+1]==0||a[x+1][y+1]>k+1))
{
a[x+1][y+1]=k+1;
aux.x=x+1;
aux.y=y+1;
st[++j]=aux;
}
if(x>0&&y<m-1&&v[x-1][y+1]==' '&&(a[x-1][y+1]==0||a[x-1][y+1]>k+1))
{
a[x-1][y+1]=k+1;
aux.x=x-1;
aux.y=y+1;
st[++j]=aux;
}
}
}
void lee2()
{
while(i<=j)
++i;
st[++j]=aux;
b[aux.x][aux.y]=1;
while(i<=j)
{
x=st[i].x;
y=st[i].y;
k=b[x][y];
++i;
if(k>=sol-1)
continue;
if(x>0&&v[x-1][y]==' '&&(b[x-1][y]==0||b[x-1][y]>k+1))
{
b[x-1][y]=k+1;
aux.x=x-1;
aux.y=y;
st[++j]=aux;
}
if(y>0&&v[x][y-1]==' '&&(b[x][y-1]==0||b[x][y-1]>k+1))
{
b[x][y-1]=k+1;
aux.x=x;
aux.y=y-1;
st[++j]=aux;
}
if(x<n-1&&v[x+1][y]==' '&&(b[x+1][y]==0||b[x+1][y]>k+1))
{
b[x+1][y]=k+1;
aux.x=x+1;
aux.y=y;
st[++j]=aux;
}
if(y<m-1&&v[x][y+1]==' '&&(b[x][y+1]==0||b[x][y+1]>k+1))
{
b[x][y+1]=k+1;
aux.x=x;
aux.y=y+1;
st[++j]=aux;
}
///////////////////////////
if(x>0&&y>0&&v[x-1][y-1]==' '&&(b[x-1][y-1]==0||b[x-1][y-1]>k+1))
{
b[x-1][y-1]=k+1;
aux.x=x-1;
aux.y=y-1;
st[++j]=aux;
}
if(x<n-1&&y>0&&v[x+1][y-1]==' '&&(b[x+1][y-1]==0||b[x+1][y-1]>k+1))
{
b[x+1][y-1]=k+1;
aux.x=x+1;
aux.y=y-1;
st[++j]=aux;
}
if(x<n-1&&y<m-1&&v[x+1][y+1]==' '&&(b[x+1][y+1]==0||b[x+1][y+1]>k+1))
{
b[x+1][y+1]=k+1;
aux.x=x+1;
aux.y=y+1;
st[++j]=aux;
}
if(x>0&&y<m-1&&v[x-1][y+1]==' '&&(b[x-1][y+1]==0||b[x-1][y+1]>k+1))
{
b[x-1][y+1]=k+1;
aux.x=x-1;
aux.y=y+1;
st[++j]=aux;
}
}
}
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
int i,j;
scanf("%d%d\n",&n,&m);
for(i=0;i<n;++i)
fgets(v[i],200,stdin);
for(i=0;i<n;++i)
for(j=0;j<m;++j)
if(v[i][j]=='R'||v[i][j]=='J')
{
++nr;
aux.x=i;
aux.y=j;
if(v[i][j]=='R')
lee1();
else
lee2();
if(nr==2)
{
i=n+1;
break;
}
}
for(i=0;i<n;++i)
for(j=0;j<m;++j)
if(a[i][j]==b[i][j]&&a[i][j]<sol&&a[i][j]>0)
{
sol=a[i][j];
solx=i;
soly=j;
}
/*for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
printf("%2d ",a[i][j]);
printf("\n");
}
printf("\n");printf("\n");
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
printf("%2d ",b[i][j]);
printf("\n");
}*/
printf("%d %d %d\n",sol,solx+1,soly+1);
return 0;
}