http://poj.org/problem?id=2435
#include <stdio.h>
#include <queue>
using namespace std;
typedef pair<int,int> point;
int dx[] = { 0, 1,-1, 0};
int dy[] = { 1, 0, 0,-1};
char way[] = { '-','|','|','-'};
char to[] = { 'E','S','N','W'};
int n,m,bx,by,ex,ey;
bool sign[100][100];
char map[100][100];
int from[100][100];
queue<point> q;
inline bool inmap( int x, int y )
{
return 0<=x && x<n && 0<=y && y<m;
}
void findpath()
{
point p;
int xx,yy,i,x,y;
while( !q.empty() )
q.pop();
q.push( point(bx,by) );
sign[bx][by] = true;
while( !q.empty() )
{
p = q.front();
q.pop();
x = p.first, y = p.second;
for( i=0; i<4; i++ )
{
if( inmap( xx=x+dx[i]*2, yy=y+dy[i]*2 ) && !sign[xx][yy] && map[x+dx[i]][y+dy[i]] == way[i] )
{
from[xx][yy] = 3 - i;
sign[xx][yy] = true;
if( xx == ex && yy == ey ) return;
q.push( point(xx, yy) );
}
}
}
}
void init()
{
int i, j;
scanf( "%d%d", &n, &m );
n = n*2-1, m = m*2-1;
for( i=0; i<n; i++ )
for( j=0; j<m; j++ )
{
scanf( "%1s", map[i]+j );
if( map[i][j] == 'S' )
ex = i, ey = j;
if( map[i][j] == 'E' )
bx = i, by = j;
}
}
void doit()
{
int i, s, x, y, j;
findpath();
x = ex, y = ey;j = -1;
while( x != bx || y != by )
{
i = from[x][y];
if( i == j ) s++;
else
{
if( j != -1 ) printf( "%dn", s );
s = 1;
printf( "%c ", to[i] );
j = i;
}
x += dx[i]*2, y += dy[i]*2;
}
printf( "%dn", s );
}
int main()
{
init();
doit();
return 0;
}