UVa 11624

UVa 11624 Solution

//Jair Said Hernandez Reyes
// BFS Multi-Sourcing.
#include<bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
#define ll long long
#define pb push_back
#define MAXN 1050
ll CC, N , M;
pair<int, int> joe;
vector<pair<int, int> >S;
char A[MAXN][MAXN];
int D1[MAXN][MAXN];
int D2[MAXN][MAXN];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
int valid(int i, int j){
	return (i >= 0 && i < N && j >= 0 && j < M && A[i][j] == '.');
}
int main(){
	cin >> CC;
	while(CC--){
		cin >> N >> M;
		S.clear();
		for(int i = 0; i < N; i++)
			for(int j = 0 ; j < M; j++){
				D1[i][j] = D2[i][j] = INF;
				cin >> A[i][j];
				if(A[i][j] == 'F')
					S.pb(make_pair(i, j));
				if(A[i][j] == 'J')
					joe = make_pair(i, j);
			}
		queue<pair<int, int> > Q;
		for(int i = 0; i < S.size(); i++){
			Q.push(S[i]);
			D1[S[i].first][S[i].second] = 0;	
		}
		while(!Q.empty()){
			pair<int, int> u;
			u = Q.front();
			Q.pop();
			for(int i = 0; i < 4; i++){
				pair<int, int> v;
				v.first = u.first + dr[i];
				v.second = u.second + dc[i];
				if(valid(v.first, v.second)){
					if(D1[u.first][u.second] + 1 < D1[v.first][v.second]){
						D1[v.first][v.second] = D1[u.first][u.second] + 1;
						Q.push(make_pair(v.first, v.second));
					}
				}
			}
		}
		Q.push(make_pair(joe.first, joe.second));
		D2[joe.first][joe.second] = 0;
		while(!Q.empty()){
			pair<int, int> u;
			u = Q.front();
			Q.pop();
			for(int i = 0; i < 4; i ++){
				pair<int, int> v = make_pair(u.first + dr[i], u.second + dc[i]);
				if(valid(v.first, v.second)){
					if(D2[u.first][u.second] + 1 < D2[v.first][v.second]){
						D2[v.first][v.second] = D2[u.first][u.second] +1;
						Q.push(make_pair(v.first, v.second));
					}
				}
			}
		}
		int timez = INF;
		for(int i = 0; i < N; i++){
			if(D2[i][0] < D1[i][0])
				timez = min(timez, D2[i][0]);
			if(D2[i][M-1] < D1[i][M-1])
				timez = min(timez, D2[i][M-1]);
		}
		for(int i = 0; i < M; i++){
			if(D2[0][i] < D1[0][i])
				timez = min(timez, D2[0][i]);
			if(D2[N-1][i] < D1[N-1][i])
				timez = min(timez, D2[N-1][i]);
			
		}
		if(timez != INF)
			cout << timez + 1;
		else
			cout << "IMPOSSIBLE";
		cout << endl;
	}
	return 0;
}