Poj Solution 2435

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;
}