uva 314 - Robot

/*Problem link

  BFS, Graph.

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 60;
const int dx[12]={0,0,0,-1,-2,-3,0,0,0,1,2,3};
const int dy[12]={-1,-2,-3,0,0,0,1,2,3,0,0,0};
const int oo = 20000000;
//-------------------------------
class dist { public: int value; char c; };
//-------------------------------
int a[maxn][maxn];
dist d[maxn][maxn];
int m,n,s1,s2,e1,e2;
char dir;
//-------------------------------
bool readfile() {
 string tmp;
 cin >> n >> m;
 if (n==0 && m==0) return(false);
 for (int i=1; i<=n; i++)
  for (int j=1; j<=m; j++) cin >> a[i][j];
 cin >> s1 >> s2 >> e1 >> e2 >> dir;
 getline(cin,tmp);
 return(true);
}
//-------------------------------
bool IsIn(int x1,int y1) {
 if (x1>=1 && y1>=1 && x1<=n-1 && y1<=m-1) return(true);
 return(false);
}
//-------------------------------
bool IsOp(char c1,char c2) {
 if (c1=='n' && c2=='s') return(true);
 if (c1=='w' && c2=='e') return(true);
 if (c1=='s' && c2=='n') return(true);
 if (c1=='e' && c2=='w') return(true);
 return(false);
}
//-------------------------------
int BFS(int s1, int s2, int e1, int e2) {
 int qx[maxn*maxn*maxn],qy[maxn*maxn*maxn];
 int head=1, tail=1,x,y,xx,yy;
 for (int i=0; i<=n+2; i++)
  for (int j=0; j<=m+2; j++) d[i][j].value=oo;
 qx[head]=s1;
 qy[head]=s2;
 d[s1][s2].value=0;
 d[s1][s2].c=dir;
 do
 {
  x=qx[head]; y=qy[head]; head++;
  for (int k=0; k<=2; k++)
  {
   xx=x+dx[k];
   yy=y+dy[k];
   char cur;
   cur='w';
   if (IsIn(xx,yy) && a[xx][yy]!=1 && a[xx+1][yy]!=1 && a[xx][yy+1]!=1 && a[xx+1][yy+1]!=1)
   {
    if (cur!=d[x][y].c) 
    {
     if (IsOp(cur,d[x][y].c))
     { 
      if (d[xx][yy].value>d[x][y].value+3)
      {
       d[xx][yy].value=d[x][y].value+3;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
     }
     else if (d[xx][yy].value>d[x][y].value+2)
      {
       d[xx][yy].value=d[x][y].value+2;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
    }
    else if (d[xx][yy].value>d[x][y].value+1)
     {
      d[xx][yy].value=d[x][y].value+1;
      d[xx][yy].c=cur;
      tail++;
      qx[tail]=xx;
      qy[tail]=yy;
     }
   }
   else break;
  }
  for (int k=3; k<=5; k++)
  {
   xx=x+dx[k];
   yy=y+dy[k];
   char cur;
   cur='n';
   if (IsIn(xx,yy) && a[xx][yy]!=1 && a[xx+1][yy]!=1 && a[xx][yy+1]!=1 && a[xx+1][yy+1]!=1)
   {
    if (cur!=d[x][y].c) 
    {
     if (IsOp(cur,d[x][y].c)) 
     {
      if (d[xx][yy].value>d[x][y].value+3)
      {
       d[xx][yy].value=d[x][y].value+3;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
     }
     else if (d[xx][yy].value>d[x][y].value+2)
      {
       d[xx][yy].value=d[x][y].value+2;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
    }
    else if (d[xx][yy].value>d[x][y].value+1)
     {
      d[xx][yy].value=d[x][y].value+1;
      d[xx][yy].c=cur;
      tail++;
      qx[tail]=xx;
      qy[tail]=yy;
     }
   }
   else break;
  }
  for (int k=6; k<=8; k++)
  {
   xx=x+dx[k];
   yy=y+dy[k];
   char cur;
   cur='e';
   if (IsIn(xx,yy) && a[xx][yy]!=1 && a[xx+1][yy]!=1 && a[xx][yy+1]!=1 && a[xx+1][yy+1]!=1)
   {
    if (cur!=d[x][y].c) 
    {
     if (IsOp(cur,d[x][y].c)) 
     {
      if (d[xx][yy].value>d[x][y].value+3)
      {
       d[xx][yy].value=d[x][y].value+3;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
     }
     else if (d[xx][yy].value>d[x][y].value+2)
      {
       d[xx][yy].value=d[x][y].value+2;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
    }
    else if (d[xx][yy].value>d[x][y].value+1)
     {
      d[xx][yy].value=d[x][y].value+1;
      d[xx][yy].c=cur;
      tail++;
      qx[tail]=xx;
      qy[tail]=yy;
     }
   }
   else break;
  }
  for (int k=9; k<=11; k++)
  {
   xx=x+dx[k];
   yy=y+dy[k];
   char cur;
   cur='s';
   if (IsIn(xx,yy) && a[xx][yy]!=1 && a[xx+1][yy]!=1 && a[xx][yy+1]!=1 && a[xx+1][yy+1]!=1)
   {
    if (cur!=d[x][y].c) 
    {
     if (IsOp(cur,d[x][y].c)) 
     {
      if (d[xx][yy].value>d[x][y].value+3)
      {
       d[xx][yy].value=d[x][y].value+3;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
     }
     else if (d[xx][yy].value>d[x][y].value+2)
      {
       d[xx][yy].value=d[x][y].value+2;
       d[xx][yy].c=cur;
       tail++;
       qx[tail]=xx;
       qy[tail]=yy;
      }
    }
    else if (d[xx][yy].value>d[x][y].value+1)
     {
      d[xx][yy].value=d[x][y].value+1;
      d[xx][yy].c=cur;
      tail++;
      qx[tail]=xx;
      qy[tail]=yy;
     }
   }
   else break;
  }
 } while (head<=tail);
 if (d[e1][e2].value==oo) return(-1);
 else return(d[e1][e2].value);
}
//-------------------------------
int main() {
 while (readfile()) cout << BFS(s1,s2,e1,e2) << endl;
 return 0;
}
//-------------------------------