#include<fstream>
#include<iomanip>
using namespace std;
fstream f("date.in", ios::in);
fstream g("date.out",ios::out);
struct poz{int i,j;};
const int di[]={0,0,-1,1};
const int dj[]={-1,1,0,0};
char dir[]="VENS";
int a[10][10], ba[10][10],n,io,jo,m,minp=100;
poz x[100], bx[100];
char y[100], by[100];
int inside(int i,int j)
{ return i>=1 && j>=1 && i<=n && j<=m;
}
void citire()
{ f>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f>>a[i][j];
f>>io>>jo;
}
void afis(int k)
{ for(int i=1;i<=n;i++)
{ g<<endl;
for(int j=1;j<=m;j++)
g<<setw(3)<<ba[i][j];
}
g<<endl;
for(int i=1;i<=k; i++)
g<<bx[i].i<<","<<bx[i].j<<" ";
g<<endl;
for(int i=1;i<k; i++) g<<by[i];
g<<endl;
}
int sol(int i,int j)
{ return i==1 || j==1 || i==n || j==m;
}
void alegemin(int k)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) ba[i][j]=a[i][j];
for(i=1;i<=k;i++)
bx[i]=x[i];
for(i=1;i<k;i++) by[i]=y[i];
minp=k;
}
void back(int i,int j,int pas)
{ if(sol(i,j))
{
if(minp>pas-1) alegemin(pas-1);
}
else for(int p=0;p<=3;p++)
{int inou,jnou;
inou=i+di[p];
jnou=j+dj[p];
if(inside(inou,jnou) && a[inou][jnou]==0 && pas<minp)
{
x[pas].i=inou;
x[pas].j=jnou;
y[pas-1]=dir[p];
a[inou][jnou]=pas;
back(inou,jnou,pas+1);
a[inou][jnou]=0;
}
}
}
int main()
{ citire();
a[io][jo]=1;
x[1].i=io;
x[1].j=jo;
back(io,jo,2);
afis(minp);
f.close();
g.close();
return 0;
}
|