CFR 329 1B. Biridian Forest ( Shortest Path )

Problem - 329B - Codeforces
Let's think about all other trainers try to meet or wait us at the exit. Certainly if one is able to move to the exit before ( or on the same time ) we do, they will battle us. What if not? We will be able to avoid them without special care, simply moving to the exit with our shortest path towards it. This implies that if we find single source shortest path from the exit to all trainers, if some trainers are nearer ( or equal to ) our shortest distance, they will battle us, otherwise not.

#include <bits/stdc++.h>
using namespace std;
const int MAXR = 1e3 + 3;
const int MAXC = 1e3 + 3;
typedef pair< int, int > pii;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

int r, c;
char G[ MAXR ][ MAXC ];

int sx, sy, ex, ey;

void init(){
    for( int i = 0; i < r; ++i )
        for( int j = 0; j < c; ++j ){
            if( G[ i ][ j ] == 'S' )
                sx = i, sy = j;
            if( G[ i ][ j ] == 'E' )
                ex = i, ey = j;
        }
}

int dis[ MAXR ][ MAXC ];

bool outOfRange( int x, int y ){
    return x < 0 || x >= r || y < 0 || y >= c;
}

void solve(){
    queue< pii > que;
    que.push( pii( ex, ey ) );
    memset( dis, 0x3f3f3f3f, sizeof(dis) );
    dis[ ex ][ ey ] = 0;
    while( !que.empty() ){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        for( int di = 0; di < 4; ++di ){
            int nx = x + dx[ di ];
            int ny = y + dy[ di ];
            if( outOfRange( nx, ny ) ) continue;
            if( G[ nx ][ ny ] == 'T' ) continue;
            if( dis[ nx ][ ny ] > dis[ x ][ y ] + 1 )
                dis[ nx ][ ny ] = dis[ x ][ y ] + 1,
                que.push( pii( nx, ny ) );
        }
    }
    int cnt = 0;;
    for( int i = 0; i < r; ++i )
        for( int j = 0; j < c; ++j )
            if( '1' <= G[ i ][ j ] && G[ i ][ j ] <= '9')
                if( dis[ i ][ j ] <= dis[ sx ][ sy ] )
                    cnt += G[ i ][ j ] - '0';
    printf("%d\n", cnt);
}

int main(){
    scanf("%d%d", &r, &c);
    for( int i = 0; i < r; ++i )
        scanf("%s", G[ i ]);
    init();
    solve();
    return 0;
}