TLE на BFS из нескольких источников

Я пытаюсь решить эту проблему: http://olimpiada-informatica.org/?cmd=downloadE&PBM = velo101&внутр = PDF Это на испанском, но я постараюсь перевести это здесь:

Вы собираетесь приземлиться на земле, когда узнаете, что кто-то выпустил несколько Велоцирапторов на взлетно-посадочной полосе.
Поездка на посадку имеет прямоугольную форму. Мы помечаем точкой (.)пустое место, с V велоцирапторы и с # пятна с препятствиями на них (вы не можете приземлиться на них).
Велоцирапторам требуется секунда, чтобы перейти в другое место, но они могут двигаться только горизонтально и вертикально.
Вас просят пометить X те места, в которых, приземлившись на них, вы максимально увеличите оставшееся время жизни.

Я сделал алгоритм, в котором я беру каждую позицию велоцирапторов и делаю BFS на каждой позиции, но я получаю TLE, вот мой код:

http://ideone.com/a6BVv3

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

int cost[501][501],xx,yy,n,m;
char mat[501][501];
bool visit[501][501],first = true;

int a[] = {-1,0,0,1}, b[] = {0,-1,1,0};

void check(int x,int y,int level) {
cost[x][y] = level;
for(int i = 0; i < 4; ++i) {
xx = x + a[i];
yy = y + b[i];
if(0 <= xx and xx < n and 0 <= yy and yy < m and mat[xx][yy] == '.') {
if(!visit[xx][yy] or level + 1 < cost[xx][yy]) {
visit[xx][yy] = true;
check(xx,yy,level + 1);
}
}
}
}

int max() {
int r = -1;
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(mat[i][j] == '.') r = max(r,cost[i][j]);
return r;
}

void show() {
if(!first) puts("---");
int r = max();
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(cost[i][j] == r) printf("X");
else printf("%c",mat[i][j]);
}
puts("");
}
}

int main() {
while(scanf("%d %d",&n,&m) == 2) {
queue<pair<int,int> > cola;
for(int i = 0; i < n; ++i) {
scanf("\n");
for(int j = 0; j < m; ++j) {
scanf("%c",&mat[i][j]);
if(mat[i][j] == 'V') cola.push(make_pair(i,j));
}
}
memset(cost,-1,sizeof cost);
memset(visit,0,sizeof visit);
while(!cola.empty()) {
pair<int,int> aux = cola.front();
visit[aux.first][aux.second] = true;
check(aux.first, aux.second,0);
cola.pop();
}
show();
first = false;
}
return 0;
}

Кто-нибудь знает, как я могу улучшить свой алгоритм?

РЕДАКТИРОВАТЬ

Хорошо, я смог решить проблему, вот код, если кому-то интересно:

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

int cost[501][501],n,m;
char mat[501][501];
bool visit[501][501],first = true;
queue<pair<int,int> > cola;

int a[] = {-1,0,0,1}, b[] = {0,-1,1,0};

int max() {
int r = -1;
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(mat[i][j] == '.') r = max(r,cost[i][j]);
return r;
}

void show() {
if(!first) puts("---");
int r = max();
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(cost[i][j] == r) printf("X");
else printf("%c",mat[i][j]);
}
puts("");
}
}

int main() {
int cont = 0,x,y,xx,yy,level;
while(scanf("%d %d",&n,&m) == 2) {
for(int i = 0; i < n; ++i) {
scanf("\n");
for(int j = 0; j < m; ++j) {
scanf("%c",&mat[i][j]);
if(mat[i][j] == 'V') cola.push(make_pair(i,j));
}
}
memset(cost,-1,sizeof cost);
memset(visit,0,sizeof visit);
while(!cola.empty()) {
int s_cola = cola.size();
for(int i = 0; i < s_cola; ++i) {
x = cola.front().first, y = cola.front().second;
cola.pop();
level = cost[x][y];
for(int i = 0; i < 4; ++i) {
xx = x + a[i], yy = y + b[i];
if(0 <= xx and xx < n and 0 <= yy and yy < m and mat[xx][yy] == '.') {
if(!visit[xx][yy] or level + 1 < cost[xx][yy]) {
visit[xx][yy] = true;
cost[xx][yy] = level + 1;
cola.push(make_pair(xx,yy));
}
}
}
}
}
show();
first = false;
}
return 0;
}