Code: Select all
#include<stdio.h>
#include<string.h>
#define MAX_R 51
#define MAX_C 51
#define INF -1
int what_dir(const char *p);
void enqueue(int r,int c,int d);
void dequeue(int& r,int& c,int& d);
long cost[MAX_R][MAX_C][4];
int queue[MAX_R*MAX_C*4+4];
int head,tail;
int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1};
char *name_dir[]={"north","east","south","west"};
int main()
{
int R,C,i,j,d;
int sr,sc,tr,tc;
int dir,ndir,min;
int matrix[MAX_R][MAX_C];
char s_dir[10];
int r,c,nr,nc;
while(scanf("%d%d",&R,&C)&&(R||C))
{
for(i=0;i<R;i++)
for(j=0;j<C;j++)
{
scanf("%d",&matrix[i][j]);
for(d=0;d<4;d++)
cost[i][j][d]=INF;
}
scanf("%d %d %d %d %s",&sr,&sc,&tr,&tc,s_dir);
dir=what_dir(s_dir);
head=tail=0;
cost[sr][sc][dir]=0;
enqueue(sr,sc,dir);
while(head!=tail)
{
dequeue(r,c,dir);
if(r==tr && c==tc)
break;
for(i=1;i<4;i++)
{
nr=r+i*dr[dir];
nc=c+i*dc[dir];
ndir=dir;
if((nr>=0 && nr<R)&&
(nc>=0 && nc<C)&&
(matrix[nr][nc]!=1)&&
(matrix[nr-1][nc-1]!=1)&&
(matrix[nr][nc-1]!=1)&&
(matrix[nr-1][nc]!=1)&&
(cost[nr][nc][ndir]==INF))
{
cost[nr][nc][ndir]=cost[r][c][dir]+1;
enqueue(nr,nc,ndir);
}
else
break;
}
ndir=(dir+1)%4;
if(cost[r][c][ndir]==INF)
{
cost[r][c][ndir]=cost[r][c][dir]+1;
enqueue(r,c,ndir);
}
ndir=(dir+3)%4;
if(cost[r][c][ndir]==INF)
{
cost[r][c][ndir]=cost[r][c][dir]+1;
enqueue(r,c,ndir);
}
}
min=INF;
for(dir=0;dir<3;dir++)
{
if(cost[tr][tc][dir]!=INF)
{
if(min==INF)
min=cost[tr][tc][dir];
else if(min>cost[tr][tc][dir])
min=cost[tr][tc][dir];
}
}
printf("%d\n",min);
}
}
void enqueue(int r,int c,int d)
{
queue[tail++]=(((r*MAX_C)+c)*4+d);
}
void dequeue(int& r,int& c,int& d)
{
int t;
d=queue[head]%4;
t=queue[head++]/4;
c=t%MAX_C;
r=t/MAX_C;
}
int what_dir(const char *p)
{
int i;
for(i=0;i<4;i++)
if(strcmp(p,name_dir[i])==0)
return i;
return -1;
}
