#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; }