Facebook Hacker Cup 2011 Round 1A After the Dance Battle

#include <iostream>
#include <vector>
#include <string>
#include <utility>
using namespace std;

int main()
{
    int N;
    cin >> N;

    for ( int testcase=0; testcase<N; testcase++ )
    {
        int R, C;
        cin >> R >> C;

        vector<string> M(R);
        for ( int i=0; i<R; i++ )
            cin >> M[i];

        int sx, sy;
        int gx, gy;

        vector<pair<int,int> > col[10];
        for ( int i=0; i<R; i++ )
        for ( int j=0; j<C; j++ )
        {
            if ( '1' <= M[i][j]  &&  M[i][j] <= '9' )
                col[M[i][j]-'0'].push_back( make_pair(i,j) );
            if ( M[i][j] == 'S' )
                sx = i, sy = j;
            if ( M[i][j] == 'E' )
                gx = i,  gy = j;
        }

        int S[128][128];
        for ( int i=0; i<128*128; i++ )
            S[0][i] = 99999999;

        S[sx][sy] = 0;

        int dx[] = { 1, -1, 0, 0 };
        int dy[] = { 0, 0, 1, -1 };

        for ( int d=0; ; d++ )
        {
            bool up = false;

            for ( int x=0; x<R; x++ )
            for ( int y=0; y<C; y++ )
            if ( S[x][y] == d )
            {
                for ( int i=0; i<4; i++ )
                {
                    int tx = x + dx[i];
                    int ty = y + dy[i];
                    
                    if ( 0<=tx  &&  tx<R  && 0<=ty && ty<C  &&
                         M[tx][ty] != 'W' &&  S[tx][ty] > d+1 )
                    {
                        S[tx][ty] = d+1;
                        up = true;
                    }
                }

                if ( '1' <= M[x][y]  &&  M[x][y] <= '9' )
                {
                    for ( int i=0; i<col[M[x][y]-'0'].size(); i++ )
                    {
                        int tx = col[M[x][y]-'0'][i].first;
                        int ty = col[M[x][y]-'0'][i].second;

                        if ( S[tx][ty] > d+1 )
                        {
                            S[tx][ty] = d+1;
                            up = true;
                        }
                    }
                }
            }

            if ( ! up )
                break;
        }

        cout << S[gx][gy] << endl;
    }
}