http://poj.org/problem?id=1307
#include"stdio.h"
bool left[13][13];
bool right[13][13];
bool up[13][13];
bool down[13][13];
int n,m,x1,x2,y1,y2;
bool init()
{
int i,j,s;
scanf("%d %d %d %d %d %d",&n,&m,&x1,&y1,&x2,&y2);
if(n==0&&m==0&&x1==0&&x2==0&&y1==0&&y2==0)
return 0;
x1--,x2--,y1--,y2--;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%d",&s);
right[i][j] = left[i][j+1]= (s&1);
down[i][j] = up[i+1][j]= (s&2);
}
for(i=0;i<n;i++)
left[i][0]=true,right[i][m-1]=true;
for(j=0;j<m;j++)
up[0][j]=true,down[n-1][j]=true;
return 1;
}
int sign[13][13];
bool (*pt[])[13]={left,up,right,down};
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
bool search(int x,int y,int step)
{
int i;
sign[x][y]=step;
if(x==x2&&y==y2)return 1;
for(i=0;i<4;i++)
if( !pt[i][x][y] && sign[x+dx[i]][y+dy[i]]==0 )
{
if(search(x+dx[i],y+dy[i],step+1))
return 1;
}
sign[x][y] = -1;
return 0;
}
void doit()
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
sign[i][j]=0;
search(x1,y1,1);
}
void printmap()
{
int i,j;
static int times=1;
printf("Maze %dnn",times++);
printf("+");
for(j=0;j<m;j++)
{
printf("---+");
}
for(i=0;i<n;i++)
{
printf("n|");
for(j=0;j<m;j++)
{
if(sign[i][j]>0)printf("%3d",sign[i][j]);
else if(sign[i][j]==-1)printf("???");
else printf(" ");
if(right[i][j])printf("|");
else printf(" ");
}
printf("n+");
for(j=0;j<m;j++)
{
if(down[i][j])printf("---");
else printf(" ");
printf("+");
}
}
printf("nnn");
}
int main()
{
while(init())
{
doit();
printmap();
}
return 0;
}