CCCPaste

Escape! If you want to survive [NCTU Floor 13]

#include 
#include 
#include 
using namespace std;

int row, col;

bool validPosition(int n, int m){
	if(n < 0 || n == row || m < 0 || m == col)
		return false;
	return true;
}

void fireSpread(vector  &map){
	vector  modified = map;
	for(int i = 0; i < row; i++){
		for(int j = 0; j < col; j++){
			if(map[i][j] == 'F'){
				if(validPosition(i - 1, j))
					modified[i - 1][j] = 'F';
				if(validPosition(i + 1, j))
					modified[i + 1][j] = 'F';
				if(validPosition(i, j - 1))
					modified[i][j - 1] = 'F';
				if(validPosition(i, j + 1))
					modified[i][j + 1] = 'F';
			}
		}
	}
	map = modified;
}

int findMinimum(vector  map, int n, int m, vector > dp, vector > visited){
	if(n == 0 || m == 0 || n == (row - 1) || m == (col - 1))
		return 0;
	if(dp[n][m] != -1)
		return dp[n][m];
	visited[n][m] = true;

	int up, down, left, right;
	up = down = left = right = 1e6;

	fireSpread(map);
	if(map[n - 1][m] == '.'){
		if(!visited[n - 1][m]){
			up = 1 + findMinimum(map, n - 1, m, dp, visited);
			//cout << "Up!" << endl;
		}
	}
	if(map[n + 1][m] == '.'){
		if(!visited[n + 1][m]){
			down = 1 + findMinimum(map, n + 1, m, dp, visited);
			//cout << "Down!" << endl;
		}
	}
	if(map[n][m - 1] == '.'){
		if(!visited[n][m - 1]){
			left = 1 + findMinimum(map, n, m - 1, dp, visited);
			//cout << "Left!" << endl;
		}
	}
	if(map[n][m + 1] == '.'){
		if(!visited[n][m + 1]){
			right = 1 + findMinimum(map, n, m + 1, dp, visited);
			//cout << "Right!" << endl;
		}
	
	}

	dp[n][m] = min(up, min(down, min(left, right)));
	return dp[n][m];
}

int solve(vector  map){
	int x = -1, y = -1;
	for(int i = 0; i < row && x == -1; i++){
		for(int j = 0; j < col; j++){
			if(map[i][j] == 'J'){
				x = i;
				y = j;
				break;
			}
		}
	}
	vector  > dp(row, vector(col, -1));
	vector  > visited(row, vector(col, false));

	int res = findMinimum(map, x, y, dp, visited);

	return (res >= 1e6 ? -1 : res);
}

int main(){
	cin >> row >> col;
	string str;
	vector  map;
	for(int i = 0; i < row; i++){
		cin >> str;
		map.push_back(str);
	}
	int res = 1 + solve(map);
	if(res - 1 == -1)
		cout << "N" << endl;
	else
		cout << res << endl;
	return 0;
}