Code: Select all
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
class mypair{
public:
int cost, vertex;
bool edge;
mypair(int COST, int VERTEX, bool EDGE){
cost = COST;
vertex = VERTEX;
edge = EDGE;
}
bool operator< (const mypair &x ) const {
return cost > x.cost;
}
};
int main(){
int cases;
scanf("%d", &cases);
for(int e= 0; e<cases; e++){
int r, c;
scanf("%d %d", &r, &c);
char grid[r][c];
for(int i =0; i<r; i++){
for(int j = 0; j<c; j++){
scanf(" %c", &grid[i][j]);
}
}
vector< vector<mypair> > adjList(r*c);
vector<int> fireIndex;
int startIndex;
bool jIsEdge = false;
for(int i = 0; i<r; i++){
for(int j = 0; j<c; j++){
int INDEX = i*c + j;
if(grid[i][j] == '#')
continue;
if(grid[i][j] == '.'){
// TOP
if(i-1 >=0){
int I = i-1;
int J = j;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// BOTTOM
if(i+1<r){
int I = i+1;
int J = j;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// LEFT
if(j-1>=0){
int I = i;
int J = j-1;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// RIGHT
if(j+1<c){
int I = i;
int J = j+1;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
} else if (grid[i][j] == 'J'){
startIndex = i*c+j;
if(i==0||j==0||i==r-1||j==c-1)
jIsEdge = true;
// TOP
if(i-1 >=0){
int I = i-1;
int J = j;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// BOTTOM
if(i+1<r){
int I = i+1;
int J = j;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// LEFT
if(j-1>=0){
int I = i;
int J = j-1;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// RIGHT
if(j+1<c){
int I = i;
int J = j+1;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
} else if (grid[i][j] == 'F'){
fireIndex.push_back(INDEX);
// TOP
if(i-1 >=0){
int I = i-1;
int J = j;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// BOTTOM
if(i+1<r){
int I = i+1;
int J = j;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// LEFT
if(j-1>=0){
int I = i;
int J = j-1;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
// RIGHT
if(j+1<c){
int I = i;
int J = j+1;
int VERTEX = I*c+J;
bool EDGE = false;
if(I==0 || I == r-1 || J == 0 || J == c-1)
EDGE = true;
if(grid[I][J] == '.' || grid[I][J] == 'J'){
adjList[INDEX].push_back(mypair(1, VERTEX, EDGE));
}
}
}
}
}
if(jIsEdge){
printf("1\n");
} else {
bool found = false;
vector<bool> visited(r*c, false);
vector<bool> firevisited(r*c, false);
priority_queue<mypair> que;
queue<mypair> fque;
que.push(mypair(0, startIndex, false));
for(int i = 0; i<fireIndex.size(); i++){
fque.push(mypair(0, fireIndex[i], false));
}
while(!que.empty() && !found ){
mypair currentNode = que.top();
que.pop();
/*
printf("Visited: ");
for(int i = 0; i<r*c; i++){
if(visited[i])
printf("%d ", i);
}
printf("Burned: ");
for(int i =0; i<r*c; i++){
if(firevisited[i])
printf("%d ", i);
}
printf("\n");*/
// If visited or burned skip
if(visited[currentNode.vertex] || firevisited[currentNode.vertex])
continue;
visited[currentNode.vertex] = true;
if(currentNode.edge){
printf("%d\n", currentNode.cost+1);
found = true;
break;
}
// Walk to adj Nodes
for(int i = 0; i<adjList[currentNode.vertex].size(); i++){
mypair adjNode = adjList[currentNode.vertex][i];
if(visited[adjNode.vertex] || firevisited[adjNode.vertex])
continue;
que.push(mypair(currentNode.cost+1, adjNode.vertex, adjNode.edge));
}
// Spread fire
int fquesize = fque.size();
for(int x=0; x<fquesize; x++){
mypair fireNode = fque.front();
fque.pop();
// Burn adj nodes
for(int i = 0; i<adjList[fireNode.vertex].size(); i++){
mypair adjNode = adjList[fireNode.vertex][i];
// If burned, skip
if(firevisited[adjNode.vertex])
continue;
firevisited[adjNode.vertex] = true;
fque.push(adjNode);
}
}
}
if(!found){
printf("IMPOSSIBLE\n");
}
}
}
return 0;
}