|
|
using namespace std;
#include<cstdio>
#include<queue>
#include<iostream>
char drum[100000];
long n,i,j,newx,newy,a[255][255],d[255][255],m,x1,y1,miin,x2,y2,k,gasit;
struct nod { int x,y; nod(){}; nod(int a,int b){x=a;y=b;};};
const int xx[4]={1,-1,0,0};
const int yy[4]={0,0,1,-1};
queue<nod>Q;
char sens(long x2, long y2, long newx, long newy)
{
if(x2-newx==1) return 'S';
if(x2-newx==-1) return 'N';
if(y2-newy==1) return 'E';
if(y2-newy==-1) return 'V';
}
int main()
{
freopen("robot.in","r",stdin);
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d ",&a[i][j]);
scanf("%d %d",&x1,&y1);
nod s,u;
s.x=x1;
s.y=y1;
Q.push(s);
d[x1][y1]=0;
while(!Q.empty())
{
u=Q.front();
Q.pop();
for(i=0;i<4;i++)
{
newx=u.x+xx[i];
newy=u.y+yy[i];
if(newx>=1&&newx<=n&&newy>=1&&newy<=m)
if(a[newx][newy]&&d[newx][newy]==0)
{
d[newx][newy]=2+d[u.x][u.y];
Q.push(nod(newx,newy));
}
else if(a[newx][newy]==0&&d[newx][newy]==0)
{
d[newx][newy]=1+d[u.x][u.y];
Q.push(nod(newx,newy));
}
else if(a[newx][newy]&&d[newx][newy]&&2+d[u.x][u.y]<d[newx][newy])
d[newx][newy]=2+d[u.x][u.y];
else if(a[newx][newy]==0&&d[newx][newy]&&1+d[u.x][u.y]<d[newx][newy])
d[newx][newy]=1+d[u.x][u.y];
}
}
miin=m*n*2;
for(i=1;i<=m;i++)
{
if(a[1][i]==0&&miin>d[1][i]){ miin=d[1][i]; x2=1;y2=i;}
if(a[n][i]==0&&miin>d[n][i]){ miin=d[n][i]; x2=n;y2=i; }
}
for(i=1;i<=n;i++)
{
if(a[i][1]==0&&miin>d[i][1]){ miin=d[i][1]; x2=i;y2=1;}
if(a[i][m]==0&&miin>d[i][m]) {miin=d[i][m]; x2=i;y2=m;}
}
printf("%d\n",miin); d[x1][y1]=0;
while(d[x2][y2])
{
gasit=0;
for(i=0;i<4&&gasit==0;i++)
{
newx=x2+xx[i];
newy=y2+yy[i];
if(newx<=n&&newy<=m&&newx>=1&&newy>=1)
if(a[x2][y2])
{ if(d[newx][newy]+2==d[x2][y2])
{
drum[k++]=sens(x2,y2,newx,newy);
x2=newx;y2=newy;
gasit=1;
}
}
else if(d[newx][newy]+1==d[x2][y2])
{
drum[k++]=sens(x2,y2,newx,newy);
x2=newx;y2=newy;
gasit=1;
}
}
}
for(i=k-1;i>=0;i--)
printf("%c",drum[i]);
return 0;
}
//succes
_______________________________________
pana cand moartea ne va desparti...
|
|
) le stiam si eu insa nu exact:-? 
that's what friends are for right? :-" 
bine :-<
